Atcoder 前缀和优化DP Candies

深碍√TFBOYSˉ_ 2024-03-30 09:26 24阅读 0赞

[Candies - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)][Candies - _ _ _ _luogu.com.cn]

题意：

![7cc590a4117c44ee9ffb351fc61603b5.png][]

思路：

考虑DP

状态设计：

首先，因为是线性DP，dp\[i\]是必不可少的

然后去考虑一下决策，看看是什么东西影响了决策

对于第 i 个位置，可以给第 i 个人0到a\[i\]个糖果，因此有a\[i\]+1个决策

什么时候不能再给了呢，当糖果用完的时候不能给，因此我们要加一维，去维护已经一共给了多少糖果

设dpi\]\[j\]，表示已经给到了第 i 个人，一共给了 j 个糖果的方案数

属性是方案数

状态转移：

所谓的状态转移就是是枚举上一个的状态，手段是枚举决策，决策不明显时也可以直接枚举上一个的状态

那么我们去枚举决策

对于第 i 个位置，决策是分0到a\[i\]个糖果给第 i 个人，即一共有a\[i\]+1个决策

对于一个位置 i 和决策 k ，上一个的状态仍未完全确定，我们还得去枚举上一层状态一共给了多少糖果

它可以是一共给了0个，也可以是一共给了K个

因此状态转移方程确定了：

![dp\[i\]\[j\]=\\sum\_\{k=0\}^\{a\[i\]\}dp\[i-1\]\[j-k\],j\\in \[0,K\]][dp_i_j_sum_k_0_a_i_dp_i-1_j-k_j_in _0_K]

初始化：

dp\[0\]\[0\]=1

因此我们DP差不多就做好了

Code：

#include <bits/stdc++.h>
    using namespace std;
    const int mxn=1e2+10,mxv=1e5+10,mod=1e9+7;
    #define int long long
    int n,K;
    int a[mxn],dp[mxn][mxv],sum[mxv];
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        cin>>n>>K;
        for(int i=1;i<=n;i++) cin>>a[i];
        dp[0][0]=1;
        for(int i=1;i<=n;i++){
            for(int j=0;j<=K;j++){
                for(int k=0;k<=min(a[i],j);k++){
                    if(j<k) continue;
                    dp[i][j]+=dp[i-1][j-k];
                    dp[i][j]%=mod;
                }
            }
        }
        cout<<dp[n][K]%mod<<'\n';
    }

但是这样暴力的DP复杂度是O(n\*k\*k)的，显然TLE

因此我们需要一些优化措施

前缀和优化：

注意到第 i 个位置的答案是由上一层i-1的区间和转移过来的，因此我们可以预处理第 i-1 层的前缀和，然后直接把第 i-1 层的前缀和数组做差即可

Code：

#include <bits/stdc++.h>
    using namespace std;
    const int mxn=1e2+10,mxv=1e5+10,mod=1e9+7;
    #define int long long
    int n,K;
    int a[mxn],dp[mxn][mxv],sum[mxv];
    int get(int l,int r){
        return l==0?sum[r]:(sum[r]-sum[l-1]+mod)%mod;
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        cin>>n>>K;
        for(int i=1;i<=n;i++) cin>>a[i];
        dp[0][0]=1ll;
        for(int i=1;i<=n;i++){
            sum[0]=dp[i-1][0];
            for(int j=1;j<=K;j++) sum[j]=(sum[j-1]+dp[i-1][j])%mod;
            for(int j=0;j<=K;j++){
                dp[i][j]=get(max(j-a[i],0ll),j);
            }
        }
        /*for(int i=1;i<=n;i++){
            for(int j=0;j<=K;j++) cout<<dp[i][j]<<" ";
            cout<<'\n';
        }*/
        cout<<dp[n][K]%mod<<'\n';
    }

疑问：

如果设状态为第 i 个位置，还剩下多少糖没给的方案数，这样过不了样例，不知道为什么，好奇怪

WA Code：

#include <bits/stdc++.h>
    using namespace std;
    const int mxn=1e2+10,mxv=1e5+10,mod=1e9+7;
    #define int long long
    int n,K;
    int a[mxn],dp[mxn][mxv],sum[mxv];
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        cin>>n>>K;
        for(int i=1;i<=n;i++) cin>>a[i],sum[i]=(sum[i-1]+a[i])%mod;
        dp[0][K]=1;
        for(int i=1;i<=n;i++){
            for(int j=K;j>=max(K-sum[i],0ll);j--){
                for(int k=min(a[i],j);k>=0;k--){
                    //if(j<k) continue;
                    dp[i][j]+=dp[i-1][j+k];
                    dp[i][j]%=mod;
                }
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=0;j<=K;j++) cout<<dp[i][j]<<" ";
            cout<<'\n';
        }
        cout<<dp[n][0]%mod<<'\n';
    }

**总结：**

**前缀和优化：**

**当第 i 层的答案是由第 i-1 层的区间和转移过来的时候，考虑使用前缀和优化DP**

[Candies - _ _ _ _luogu.com.cn]: https://www.luogu.com.cn/problem/AT_dp_m
[7cc590a4117c44ee9ffb351fc61603b5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/7d3e86dbf34a4fef97bd95c904adecde.png
[dp_i_j_sum_k_0_a_i_dp_i-1_j-k_j_in _0_K]: https://latex.csdn.net/eq?dp%5Bi%5D%5Bj%5D%3D%5Csum_%7Bk%3D0%7D%5E%7Ba%5Bi%5D%7Ddp%5Bi-1%5D%5Bj-k%5D%2Cj%5Cin%20%5B0%2CK%5D