题解 P1725 【琪露诺】

倔强的咸鱼 · 2019-10-11 15:17:41 · 题解

滚动数组优化

看了几篇题解，大佬貌似都是用优先队列或者单调队列优化的dp，蒟蒻对单调队列这一块真的特别弱，所以写了一个裸的背包dp。。。

简单可知状态转移方程为：dp[i] = max(dp[i-r,i-l])+dp[i];

简单思考一下dp的原理，我只需要保证到达当前状态的值的最大的，我就能保证保证到达i+r，i+l时的近似最优，在多个近似最优里面挑出最优即可。因为这是一个从前往后跳的过程，前面的状态不会被后面的状态影响，考虑滚动数组优化。

最后就是找答案方面，应该在n到n+r的范围内找出最大即可（即dp数组设置为双倍大小）

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e6+5;
const int INF = -0x3f3f3f3f;

int dp[maxn << 1],a[maxn];

int main()
{
    int n,l,r;
    scanf("%d%d%d",&n,&l,&r);
    memset(dp,INF,sizeof(dp));
    memset(a,0,sizeof(a));
    for(int i = 0;i <= n;++i) scanf("%d",&a[i]);

    dp[0] = a[0];
    for(int i = 0;i <= n;++i){
        if(dp[i] != INF){
            for(int j = i+l;j <= i+r;++j){
                dp[j] = max(dp[j],dp[i]+a[j]);
            }
        }
    }

    int ans = INF;
    for(int i = n;i <= n+r;++i) ans = max(ans,dp[i]);
    printf("%d\n",ans);
    return 0;
}

也是这题测试数据比较水，这样就能不超时卡过去了，正解应该还是要队列优化的。

可能该想法还有我没想到的漏洞。。。大佬看见了请留言。。。thx