题目本身是一道水题,但是水题中也可以有可以思考的东西。
为何要把跑和跳拆开处理?
优化复杂度。
动态规划的原则应该满足无后效性和最优子结构。事实上在划分子问题的时候,我们完全可以将每一秒的状态划分为以下三种:
- 停(m+4)
- 走(dist+17)
- 跳(dist+60,m-10)
但为了满足无后效性的这一条件,我们将不得不把每一个状态中的m和dist保存来实现状态转移,这样的开销完全不必要的。
而若我们将他们拆开处理,就可以不用每次保存m这一个状态。
为什么要先处理跳而不是跑?
因为跳的远。
因为得不到最优子结构。
在最后一秒,若m不够支撑一次跳跃,那么显然最优解是跑一秒。但若优先处理跑,在最后一秒会将本可以跑的机会白白浪费在等待恢复m上。
#include <bits/stdc++.h>
#define MAXN 300001
using namespace std;
int m,s,t;
int dp[MAXN];
int main() {
ios::sync_with_stdio(false);
cin >> m >> s >> t;
for ( int i = 1; i <= t; ++i ) {
if ( m >= 10 ) {
dp[i] = dp[i - 1] + 60;
m -= 10;
} else {
dp[i] = dp[i - 1];
m += 4;
}
}
for ( int i = 1; i <= t; ++i ) {
dp[i] = max(dp[i], dp[i - 1] + 17);
if ( dp[i] >= s ) {
cout << "Yes" << endl << i << endl;
return 0;
}
}
cout << "No" << endl << dp[t] << endl;
return 0;
}