【简单DP】Kuangbin 免费馅饼

╰半夏微凉° 2024-03-26 16:18 79阅读 0赞

**这道题的状态设计和状态转移都挺简单的，不过有些细节需要注意**

**比如这道题在转移的过程中如果什么都不干就需要继承状态**

**然后取max的时候需要保存状态**

**然后要注意边界情况的转移的讨论**

[4552. 免费馅饼 - AcWing题库][4552. _ - AcWing]

题意：

![3d8ab2b5b08f8eccb0c62475242507e7.png][]

思路：

考虑DP：

状态设计：

设dp\[i\]\[j\]表示第i的时间，所在的坐标为j的最大收益

为什么这么设，**以时间轴为阶段很典，**然后他的决策有两种：向左走或向右走或不动，那么是什么影响了决策：所在坐标

然后去转移：

dp[i][j]=max(dp[i][j],max(dp[i-1][j-1],dp[i-1][j+1])+G[a[k].x][a[k].T]);

这个转移方程是正确的

但是如果做的决策是不动的话，就是去继承上一个阶段的状态

然后对于j=0和j=10的情况需要单独拿出来讨论

在转移的时候要保存原来的dp\[i\]\[j\]状态

Code：

#include <bits/stdc++.h>
    #include <cmath>
    //#define int long long
    using i64 = long long;
    using namespace std;
    const int mxn=1e5+10;
    const int mxe=1e6+10;
    const int mod=1e9+7;
    const double eps=1e-8;
    struct ty{
        int x,T;
    }a[mxn];
    
    int n,t=0,ans=0;
    int dp[mxn][11],G[mxn][11];
    void solve(){
        while(cin>>n&&n!=0){
            t=0;ans=0;
            memset(G,0,sizeof(G));
            memset(dp,-0x3f,sizeof(dp));
            for(int i=1;i<=n;i++){
                cin>>a[i].x>>a[i].T;
                t=max(t,a[i].T);
                G[a[i].T][a[i].x]++;
            }
            dp[0][5]=G[0][5];
            for(int i=1;i<=t;i++){
                for(int j=0;j<=10;j++){
                    dp[i][j]=max(dp[i][j],dp[i-1][j]);
                    if(j!=0) dp[i][j]=max(dp[i][j],dp[i-1][j-1]);
                    if(j!=10) dp[i][j]=max(dp[i][j],dp[i-1][j+1]);
                    dp[i][j]+=G[i][j];
                    ans=max(ans,dp[i][j]);
                }
            }
            cout<<ans<<'\n';
        }
    }
    void init(){}
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        init();
        while(__--)solve();return 0;
    }

[4552. _ - AcWing]: https://www.acwing.com/problem/content/4555/
[3d8ab2b5b08f8eccb0c62475242507e7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/ae42890a24404aa4bea174c34fb2c1c0.png