rt,这道题能否对原来的 DP 数组进行滚动数组优化呢,不介入新的变量 m 的,可参考一下代码:
#include<bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5;
const int M = 1e3 + 5;
int m,s,t,f[N][M],ans;
//f[i][j] 表示时间为 i 魔法值为 j 所跑的最远距离
//f[i][j] = max(f[i - 1][j] + 17,f[i - 1][j + 10] + 60,f[i - 1][j - 4]);
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin >> m >> s >> t;
for(int i = 1;i <= t;i++){
for(int j = 0;j <= m;j++){
if(j + 10 <= m)f[i][j] = max(f[i][j],f[i - 1][j + 10] + 60);
if(j >= 4)f[i][j] = max(f[i][j],f[i - 1][j - 4]);
f[i][j] = max(f[i][j],f[i - 1][j] + 17);
if(f[i][j] >= s){
cout << "Yes\n";
cout << i << "\n";
return 0;
}
if(i == t)ans = max(ans,f[i][j]);
}
}
cout << "No\n";
cout << ans << "\n";
return 0;
}