[练习]DP-背包类

https://ac.nowcoder.com/acm/contest/5968/E
选出来要买的m个物品中任意两个的位置差都大于等于k就行了。
现在告诉你这n个物品排成一行之后的受欢迎程度(可能是负数),求牛牛带回去的m个物品的最大欢迎度之和。

错误写法:(记录一下思考过程

int a[N];
int dp[N][105][2]; // 用0 1 表示拿不拿;dp[i][j][0/1]前i个拿j件的最大值
int main()
{
    int n,m,k;
    cin>>n>>m>>k;
    for(int i=1;i<=n;++i){
        cin>>a[i];
    }
    for(int i=0;i<=n;++i){
        for(int j=0;j<=m;++j){
            dp[i][j][0]=dp[i][j][1]=INT_MIN;
        }
    }
    for(int i=1;i<=n;++i){
        dp[i][1][1]=a[i];
         for(int j=m;j>=2;--j)
         {
            if(i-k >= 1) dp[i][j][1] = max(dp[i-k][j-1][0],dp[i-k][j-1][1])+a[i];
         }
        for(int j=1;j<=i;++j){
            dp[i][j][0] = dp[i-1][j][0]; 
           // dp[i][j][1] = max(dp[i][j][1],dp[i-1][j][0]);
        }
    }
    //cout<<dp[0][1][1]<<endl; cout<<dp[2][2][1]<<endl;cout<<dp[4][3][1]<<endl;
    cout<<max(dp[n][m][1],dp[n][m][0]);
}

状态转移:

//AC

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

const int N = 1e4+5;

#define INF 1e18

LL dp[N][105],f[N][105],a[N];// dp[i][j]等价于dp[i][j][1]  f[i][j] dp[i][j]前i个拿j件的最大值
int main()
{
    int n,m,k;
    cin>>n>>m>>k;
    for(int i=0;i<=n;++i)
        for(int j=0;j<=m;++j) dp[i][j] = -INF,f[i][j] = -INF;
    for(int i=1;i<=n;++i) cin>>a[i];
    for(int i=1;i<=n;++i)
    {
        dp[i][1] = a[i];
        for(int j=m;j>=2;--j)
        {
            if(i-k >= 1) dp[i][j] = f[i-k][j-1]+a[i];
        }
        for(int j=1;j<=i;++j) f[i][j] = max(f[i-1][j]/*不选*/,dp[i][j]);
    }
    cout<<f[n][m];
    return 0;
}
全部评论

相关推荐

不愿透露姓名的神秘牛友
今天 12:11
我最近都有点不想活了,天天早10晚11的,还问我爱不爱她目前的状态别说爱谁了,没扇谁就不错了。是不是大家都是一进节子,只有工作没有爱情了
AzureSkies:在字节的时候找的就是字节的,飞书太适合恋爱人士了,能看到是不是已读,是不是在会议中。简直冥婚好伴侣
投递字节跳动等公司9个岗位
点赞 评论 收藏
分享
qq乃乃好喝到咩噗茶:院校后面加上211标签,放大加粗,招呼语也写上211
点赞 评论 收藏
分享
牛客92804383...:在他心里你已经是他的员工了
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务