BSOI

BSOI"/>

BSOI

【问题描述】
　　小明今天得到一个跳舞毯游戏程序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，踏中所有的箭头不一定能得最高分，小明很想知道最高能得多少分，你能帮助小明计算一下最多可得多少分吗？
【文件输入】
　　第一行两个整数N和K。
　　第二行N个整数，为S的相应分数。
　　第三行也有N个整数，为B的相应分数。
【文件输出】
　　只一个整数，可得到的最高分数。
【样例输入】
　　6 3
　　1 2 3 4 5 6
　　1 1 1 20 1 1
【样例输出】
　　39
【数据范围】
对于20%的数据0≤N,T≤100；
对于100%的数据0≤N,T≤5000；
S和B各有N个数，所有分数为[0，10000]之间的整数。

DP
设f[i][j]表示在前i个箭头中，踩中j个箭头所能得到的最大分。
f[i][j]=max{f[i-1][j]-s[i],f[i-1][j-1]+a[i]+p} (取或不取第j个，p为奖励分数)

#include<cstdio>
#include<algorithm>
#define N 5001
#define INF 0x3f3f3f3f
using namespace std;
int n,t,s[N],b[N],sum[N],f[N],ans=-INF;
int main()
{freopen("dance.in","r",stdin);freopen("dance.out","w",stdout);scanf("%d%d",&n,&t);for(int i=1;i<=n;i++)scanf("%d",&s[i]);for(int i=1;i<=n;i++)scanf("%d",&b[i]);  for(int i=1;i<=n;i++)for(int j=i;j>=0;j--){int p=j%t?0:b[i];f[j]=f[j]-s[i];if(j>0) f[j]=max(f[j],f[j-1]+s[i]+p);ans=max(ans,f[j]);}printf("%d",ans);fclose(stdin); fclose(stdout);return 0;
}