题解 | #牛牛的旅游纪念品#

感觉是道比较简单的dp,但意外的比较容易做错，主要是细节很容易错。

状态表示：dp[i][j]来表示从前i个物品中取到j个能得到的最大受欢迎程度。

状态转移：对于第i个物品只有拿或者不拿两种选择，因为j我们保证一定能取这么多，所以如果拿第i个物品的话：

dp[i][j]=dp[i-k][j-1]+a[i];从前i-k个物品中拿j-1个的最大值再加上a[i]。

如果不拿第i个物品：

if((j-1)*k<=i-2) dp[i][j]=max({dp[i][j],dp[i-1][j]});判断从i-1个物品中能不能拿到j个，如过可以取最大值。

AC代码：

#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) ((x)&-x)
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const ll INF = 0x3f3f3f3f3f3f3f3fLL;
ll dp[10005][101]={0};
ll a[10005]={0};
int n,m,k;
void solve(){
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    dp[1][1]=a[1];
    for(int i=2;i<=n;i++){
        dp[i][1]=max({dp[i-1][1],a[i]});
        for(int j=2;j<=m&&(j-1)*k<=i-1;j++){
            dp[i][j]=dp[i-k][j-1]+a[i];
            if((j-1)*k<=i-2) dp[i][j]=max({dp[i][j],dp[i-1][j]});
        }
    }
    cout<<dp[n][m];
}
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    solve();
    return 0;
}