跳舞 纪中2545 dp

Description

　　小明今天得到一个跳舞毯游戏程序Dance。游戏每次连续出N 个移动的“箭头”，箭头依次标号为1 到N，并且的相应的分数S[1..N]。如果你能“踏中”第i 号箭头，你将获得相应的分数S[i]；否则将被扣除相应的分数。 　　另外，游戏还有一个累计奖励机制：如果踏准次数累计达到T，并且是在踏中第i个箭头达到的，则将得到B[i]的奖励分数,累计也将清零，重新开始。 　　例如：N＝6，T=3，相应的S 和B 分别为{1,2,3,4,5,6}、{0,0,4,7,9,10},如果小明踏中所有箭头，则得分为：(1+2+3+4)+(4+5+6+10)＝35 　　小明是个Dance 高手，可以踏中他想踏中的任意一个箭头。但他发现，根据给定的N，T，S，B，踏中所有的箭头不一定能得最高分，小明很想知道最高能得多少分，你能帮助小明计算一下最多可得多少分吗？

Input

　　第一行两个整数N 和T。 　　第二行N 个整数，为S 的相应分数。 　　第三行也有N 个整数，为B 的相应分数。

Output

　　只一个整数，可得到的最高分数。

分析

一眼知道是dp 方程很简单

f[i,j]=max(f[i−1,j]−a[i],f[i−1,j−1]+a[i])(当jmodt<>0) f[i,j]=max(f[i−1,j]−a[i],f[i−1,j−1]+a[i]+b[i])(当jmodt=0)

代码

var i,j,k:longint; n,m:longint; a,b:array[1..6000] of longint; ans:longint; f:array[1..2,-1..6000] of longint; function max(x,y:longint):longint; begin if x>y then exit(x) else exit(y); end; begin readln(n,m); for i:=1 to n do read(a[i]); readln; for j:=1 to n do read(b[j]); for i:=1 to n do begin for j:=0 to n do begin f[1,j]:=f[2,j]; f[2,j]:=0; end; f[2,0]:=f[1,0]-a[i]; for j:=1 to i do if (j mod m<>0) or (j=0) then f[2,j]:=max(f[1,j]-a[i],f[1,j-1]+a[i]) else f[2,j]:=max(f[1,j]-a[i],f[1,j-1]+a[i]+b[i]); end; ans:=0; for i:=1 to n do if f[2,i]>ans then ans:=f[2,i]; write(ans); end.