[洛谷P1095]守望者的逃离

题目本身是一道水题,但是水题中也可以有可以思考的东西。

为何要把跑和跳拆开处理?

优化复杂度。

动态规划的原则应该满足无后效性最优子结构。事实上在划分子问题的时候,我们完全可以将每一秒的状态划分为以下三种:

  • 停(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;
}
Last modification:July 29th, 2019 at 11:00 pm
博客维护不易,如果你觉得我的文章有用,请随意赞赏

Leave a Comment