洛谷 P2029 跳舞 题解【DP】【背包】

作者: wjyyy 分类: DP,背包,解题报告 发布时间: 2018-06-30 15:08

点击量:17

 

   基础的(类似背包的)DP题。

 

题目描述

小明今天得到一个跳舞毯游戏程序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的相应分数。

 

输出格式:

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

 

输入输出样例

输入样例#1:
6 3
1 2 3 4 5 6
1 1 1 20 1 1
输出样例#1:
39

说明

【样例解释】

跳过第一个,扣1分,连踩3个,得9分,并获得附加分20分,之后再连踩2个,共39分。

 

【数据范围】

对于20%的数据0≤N,T≤100;

 

对于100%的数据0≤N,T≤5000;

 

S和B各有N个数,所有分数为[0,10000]之间的整数。

 

解法:

   这个题考试时看成了每次都要连续踩中(都是样例说明的锅),于是拿了10分?还拿着错误的数据拍了半天

   DP的思路就是背包,f[i][j]表示前i个踩中了j个方块。因为累计踩中第\(m\times k\)个\((m\in \mathbb{N*})\)时会触发buff,所以每次当j枚举到k的倍数时,将数值加上buff加成再进行比较,写成三目就是:

f[i][j]=max(f[i-1][j]-a[i],f[i-1][j-1]+a[i]+(j%k==0?b[i]:0));

   最后统计答案时取f[n][]的max

 

   得出结论,一定要好好看题。不能信样例解释(虽然有时候很有用)。。

 

Code:

#include<cstdio>
#include<cstring>

int max(int x,int y)
{
    return x>y?x:y;
}
int f[5555][5555];
int a[5555],b[5555];
int main()
{
    memset(f,-0x3f,sizeof(f));
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
        scanf("%d",&b[i]);
    f[0][0]=0;
    for(int i=1;i<=n;i++)
    {
        f[i][0]=f[i-1][0]-a[i];
        for(int j=1;j<=i;j++)
            f[i][j]=max(f[i-1][j]-a[i],f[i-1][j-1]+a[i]+(j%k==0?b[i]:0));
    }
    int ans=0;
    for(int i=0;i<=n;i++)
        ans=ans>f[n][i]?ans:f[n][i];
    printf("%d\n",ans);
    return 0;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */