【简单DP】[NOIP2007 普及组] 守望者的逃离

Love The Way You Lie 2024-03-30 14:12 48阅读 0赞

[P1095 \[NOIP2007 普及组\] 守望者的逃离 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)][P1095 _NOIP2007 _ _ - _ _ _ _luogu.com.cn]

题意：

![5bb02f160d5c7f553726235637edadab.png][]

思路：

独立做出来的一道DP！

一开始我去模拟过程找子问题，然后去找阶段是什么

本来想的是以路程作为阶段，但是1e8数组开不下

那么剩下的只有把时间轴当作阶段了

确定阶段之后，我们去确定状态

我们发现，在同一阶段，蓝的数量会影响决策

因为如果没有蓝就不能用蓝了

所以我们设dp\[i\]\[j\] 表示在时刻 i 之内，拥有 j 点蓝，能走的最大距离

因为是最大值，因此数组要初始化成-inf

然后第0秒的蓝是0，这个是合法状态，初始化为0就行

然后把答案和S去对比一下，看看输出YES还是NO

这个状态设计包含了所有情况，因此是可行滴

然后我们去状态转移

即我们去枚举决策和上一层的状态

有三种决策：用10点蓝换距离，跑步，恢复蓝

当然恢复蓝的前提是前面的蓝>=4

因此状态转移方程就是：

for(int i=1;i<=T;i++){
            for(int j=0;j<=M;j++){
                if(j<4) dp[i&1][j]=max(dp[(i-1)&1][j]+17,dp[(i-1)&1][j+10]+60);
                else dp[i&1][j]=max(dp[(i-1)&1][j]+17,max(dp[(i-1)&1][j-4],dp[(i-1)&1][j+10]+60));
                if(!ok&&dp[i&1][j]>=S) ansT=i,ok=1;
            }
        }

然后因为如果能跑出的话，要输出时间

因此我们要求第一个>=S的时间

这里在转移的时候维护一下就行

因为开数组会开不下，所以可以滚动数组

这样就写好了

Code：

#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    const int mxn=3e5+10,mxv=1e3+10;
    int M,S,T,ansT,ok=0;
    int dp[2][mxv];
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        memset(dp,128,sizeof(dp));
        cin>>M>>S>>T;
        dp[0][M]=0;
        for(int i=1;i<=T;i++){
            for(int j=0;j<=M;j++){
                if(j<4) dp[i&1][j]=max(dp[(i-1)&1][j]+17,dp[(i-1)&1][j+10]+60);
                else dp[i&1][j]=max(dp[(i-1)&1][j]+17,max(dp[(i-1)&1][j-4],dp[(i-1)&1][j+10]+60));
                if(!ok&&dp[i&1][j]>=S) ansT=i,ok=1;
            }
        }
        int mx=-1;
        for(int j=0;j<=M;j++) mx=max(mx,dp[T&1][j]);
        if(mx<S){
            cout<<"No"<<'\n';
            cout<<mx<<'\n';
        }else{
            cout<<"Yes"<<'\n';
            cout<<ansT<<'\n';
        }
        return 0;
    }

**总结：**

**数组开太大，如果只取决于i-1层的状态，就可以开滚动数组**

**如果还取决于别的，那就考虑数据结构优化**

**如果DP过于暴力的时候也考虑数据结构优化**

[P1095 _NOIP2007 _ _ - _ _ _ _luogu.com.cn]: https://www.luogu.com.cn/problem/P1095
[5bb02f160d5c7f553726235637edadab.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/7372ee7f6ce14ad491313ecd57264a1e.png