关于这道题的DP
查看原帖
关于这道题的DP
917025
XYzero楼主2024/9/12 22:44

rt,这道题能否对原来的 DP 数组进行滚动数组优化呢,不介入新的变量 mm 的,可参考一下代码:

#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;
}
2024/9/12 22:44
加载中...