很久以前看过的一道dp。今天决定要A掉它。
所以开始思考，每个点有三种情况：跑步、休息或者神马也不干就那么待着。
用f[i,j]表示在第i分钟,疲劳值为j的跑出的最远距离。那么对于j>0只能由f[i-1,j-1]转移过来，因为它要跑就一直跑……
对于f[i,0]，可以等于f[i-1,0]，这是神马也不干的，也可以从以前的时间休息到这，f[i,0]:=max(f[i,0],f[i-k,k])，其中0<k<=m。
然后第一重枚举时间，第二重分情况转移就行了。
对于初始化，所有点为-1，为不可达状态，f[0,0]:=0。
View Code var f:array[0..2000,0..500] of longint; d:array[1..2000] of longint; j,k,m,n,i:longint;function max(a,b:longint):longint;beginif a>b then exit(a) else exit(b);end;begin readln(n,m);for i:=1 to n do read(d[i]); fillchar(f,sizeof(f),$ff); f[0,0]:=0;for i:=1 to n dobegin f[i,0]:=f[i-1,0];for k:=1 to m doif (i-k>=0) and (f[i-k,k]>-1) then f[i,0]:=max(f[i-k,k],f[i,0]);for j:=1 to m doif f[i-1,j-1]>-1 then f[i,j]:=max(f[i,j],f[i-1,j-1]+d[i]);end; writeln(f[n,0]);end.
4行的题目看了半小时，写了24行……dp都是精华你伤不起啊！
转载于:https://www.cnblogs.com/zjerly/archive/2011/10/19/2218198.html
