小明是个Dance 高手,可以踏中他想踏中的任意一个箭头。但他发现,根据给定的N,T,S,B,踏中所有的箭头不一定能得最高分,小明很想知道最高能得多少分,你能帮助小明计算一下最多可得多少分吗?
题解:
动态规划。i , j 分别代表前i个跳了j个,第j个有选和不选两种情况:
f[i,j]:=max(f[i-1,j]-s[i],f[i-1,j-1]+ans+s[i]);
注意:加上奖励分数。
代码:
var f:array[0..5000,0..5000] of longint; s,b:array[1..5000] of longint; n,t,i,j,ans,sum:longint; function max(x,y:longint):longint; begin if x>y then max:=x else max:=y; end; begin readln(n,t); for i:=1 to n do read(s[i]); for i:=1 to n do read(b[i]); for i:=1 to n do for j:=0 to i do begin ans:=0; if j mod t=0 then ans:=b[i]; f[i,j]:=f[i-1,j]-s[i]; if j>0 then f[i,j]:=max(f[i-1,j]-s[i],f[i-1,j-1]+ans+s[i]); end; sum:=-maxlongint; for i:=1 to n do if f[n,i]>sum then sum:=f[n,i]; writeln(sum); end.