P1095 [NOIP2007 普及组] 守望者的逃离

请添加图片描述

状态表示： $f [i] [j]$ 表示在 $i$ 时间内，还剩 $j$ 点法力值所走的最远距离是多少

状态计算：注意，我设还剩j点法力值，所以当前的状态是 $f [i] [j]$ 的转移的时候应当注意

当我们选择直接步行： $f [i] [j] = f [i ? 1] [j] + 17$ ，因为不消耗体力
当我们选择不走回复魔法： $f [i] [j] = f [i ? 1] [j ? 4]$ ，因为我们现在法力是 $j$ ，那么我们恢复前就是 $j ? 4$
当我们选择瞬移：$ f[i][j] = f[i-1][j+10]$，跟上一条分析类似

那么我们就可以来进行dp了qwq

Code

#pragma GCC optimize (2)
// 不开o2会t两个点，现在一般比赛都开o2的吧（自信）

int m, s, t;
// int f[3 * N][1020];
int f[2][1020]; // 我们发现每一次都只和上一次有关，所以我们用滚动数组来优化一下空间不然会mle

void solve(){
    cin >> m >> s >> t;
    int time = 0;
    for (int i = 1; i <= t; i++){
        for (int j = 0; j <= m; j++){
            f[i & 1][j] = f[(i - 1) & 1][j] + 17; // 用腿跑
            if(j >= 4) // 不走
                f[i & 1][j] = max(f[i & 1][j], f[(i - 1) & 1][j - 4]);
            if(j + 10 <= m) // 魔法瞬移
                f[i & 1][j] = max(f[i & 1][j], f[(i - 1) & 1][j + 10] + 60);
            if(f[i & 1][j] >= s){
                if(!time){
                    time = i;
                }
            }
        }
    }

    int res = 0;
    for (int i = 0; i <= m; i++){
        res = max(res, f[t & 1][i]);
    }
    // cout << res << endl;
    // cout << time << Endl;
    if(res >= s){
        cout << "Yes" << endl;
        cout << time;
    }
    else{
        cout << "No" << endl;
        cout << res;
    }
}