点击打开题目链接
题目大意：题目给出每个浪开始的时间，可以获得的幸福点以及每个浪的花费时间，求得最大的幸福点值。
以前抗拒DP，但是人还是要进步的。
思路：dp[i]为第i秒所能获得的最大幸福点值。状态方程dp[i]=max(dp[i+1],dp[i+wait[i]]+fun[i]);
附上AC代码：
#include<iostream> #include<algorithm> using namespace std; typedef long long ll; const int MAXN = 1e6+5; ll fun_point[MAXN]; ll wait_time[MAXN]; ll dp[MAXN]; int main() { int n; ios::sync_with_stdio(false); //read cin >> n; for (int i = 0; i < n; i++) { int a; cin >> a; cin >> fun_point[a] >> wait_time[a]; } //dp solve for (int i = 1000000; i > 0; i--) { if (fun_point[i]) { if (i + wait_time[i] > 1000000) { dp[i] = max(dp[i + 1], fun_point[i]); } else { dp[i] = max(dp[i + 1], dp[i + wait_time[i]] + fun_point[i]); } } else { dp[i] = dp[i + 1]; } } cout << dp[1] << endl; // system("pause"); return 0; }