[洛谷P1280]尼克的任务

我们从动态规划三要素角度分析这个问题:

项目分析
状态$dp[i]$表示$i \sim n$时刻最长空暇时间
阶段当前处理的时刻$i$
决策$\begin{equation} dp[i]\begin{cases} dp[i+1]+1(当前时刻无工作)\\ dp[i+worktime_{j}](当前时刻有工作) \end{cases} \end{equation}$

很明显,当前决策是基于该时刻后的时间段进行状态转移的,所以我们需要逆推时间。

这样划分子问题,正好满足了“子问题重叠性”、“无后效性”以及“最优子结构性”这三大条件。

再对边界以及目标进行分析:

项目分析
边界$dp[n]=0$,即最后一刻无空闲
目标$dp[1]$,即$1 \sim n$时刻的空闲时间

最后给出参考代码:

#include <bits/stdc++.h>
#define MAXN 10001
using namespace std;

int n,k;
pair<int,int> work[MAXN];

int num;
int dp[MAXN];
int cur[MAXN];

bool cmp(const pair<int,int> a, const pair<int,int> b) {
    return a.first > b.first;
}

int main() {
    ios::sync_with_stdio(false);

    cin >> n >> k;

    for ( int i = 1; i <= k; ++i ) {
        cin >> work[i].first >> work[i].second;
        ++cur[work[i].first];
    }

    sort( work + 1, work + 1 + k, cmp );

    for ( int i = n; i >= 1; --i ) {
        if ( cur[i] == 0 ) {
            dp[i] = dp[i + 1] + 1;
        } else 
            for ( int j = 1; j <= cur[i]; ++j ) {
                ++num;
                dp[i] = max(dp[i], dp[i + work[num].second]);        
            }
    }

    cout << dp[1] << endl;

    return 0;
}
Last modification:August 22nd, 2019 at 07:51 pm
博客维护不易,如果你觉得我的文章有用,请随意赞赏

Leave a Comment