[练习]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;
}