①2017=1.11-2.11

2/50

1.挖地雷（DP）

var
begin
fillchar(a,sizeof(a),false);
fillchar(f,sizeof(f),0);
readln(n);
for i:=1 to n do read(w[i]);
readln(x,y);
while (x<>0)or(y<>0)do begin
a[x,y]:=true;
readln(x,y);
end;
f[n]:=w[n];
for i:=n-1 downto 1 do begin
l:=-1;
for j:=i+1 to n do
if a[i,j] and (f[j]>l) then begin
l:=f[j];
k:=j;
end;

r[i]:=k;

f[i]:=l+w[i];

end;

maxn:=1;

for i:=2 to n do
if f[i]>f[maxn] then maxn:=i;
writeln(f[maxn]);
write(maxn);
while r[maxn]<>0 do begin
write(‘-‘,r[maxn]);
maxn:=r[maxn];
end;
end.

题目规定所有路径都是单向的，满足无后效性和最优化原理

a[i,j]表示i，j两个地窖之间是否有路径

动态转移方程为：f[i]=max{w[i]+f[j]}

(i<j<=n,a[i,j]=true)

边界：f[n]=w[n]

推荐逆推嘿嘿嘿（个人喜好了）

 2.合唱队形（DP）

var
  n,i,l,j,max:longint;
  b,a,f:array[1..1000] of longint;
begin
  readln(n);
  fillchar(b,sizeof(b),0);
  for i:=1 to n do read(a[i]);
  b[1]:=1;
  for i:=2 to n do begin
    l:=0;
    for j:=1 to i-1 do
    if (a[j]<a[i])and(b[j]+1>l) then l:=b[j];
    b[i]:=l+1;
  end;
  fillchar(f,sizeof(f),0);
  f[n]:=1;
  for i:=n-1 downto 1 do begin
    l:=0;
    for j:=i+1 to n do
    if (a[j]<a[i])and(f[j]+1>l) then l:=f[j];
    f[i]:=l+1;
  end;
  max:=0;
  for i:=1 to n do
  if b[i]+f[i]>max then max:=b[i]+f[i];
  dec(max);
  writeln(n-max);
end.
从两边找最长上升子串。。
中间那个被算过两次，注意-1。。

①2017=1.11-2.11

原文：http://www.cnblogs.com/AlenaNuna/p/6273124.html