jzoj 2545. 【NOIP2011模拟9.3】跳舞

发布于 2019-03-26  881 次阅读


题目描述

小明今天得到一个跳舞毯游戏程序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 和T。
第二行N 个整数,为S 的相应分数。
第三行也有N 个整数,为B 的相应分数。

输出

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

思路

很明显的dp,前i个连续了j次f[i,j]=max(f[i1,j1]+a[i],f[i1,j]a[i])加上判断是否可以有累加奖励就可以了

 #include
int f[10000][100];
int b[10000];
int a[10000];
int main()
{   
    freopen("dance10.in","r",stdin);
    int i,j,k,n,m,max,t;
    scanf("%d%d",&n,&m);
    for (i=1;i<=n;i++)
      scanf("%d",&a[i]);
    for (i=1;i<=n;i++)
      scanf("%d",&b[i]);
    for (i=1;i<=n;i++)
    {
      for (j=0;j<=i;j++)
        {
            t=0;
            if (j%m==0) t=b[i];
            max=f[i-1][j]-a[i];
            if (j>0) 
             {
                 if (maxmax) max=f[n][i];
    }
    printf("%d",max);
    return 0;
}
]]>