1301: 尼克的任务 常规做法

解题思路:

注意事项:

参考代码:

#include"bits/stdc++.h"
using namespace std;
// 定义两个数组，dp用于存储动态规划结果，kk用于记录每个位置的工作个数
int dp[10005], kk[10005];
// 定义结构体f，包含两个整数p和t，分别表示开始时间和持续时间
struct f {
    int p, t;
} h[10005];
int main() {
    int n, k;
    // 输入n和k的值
    cin >> n >> k;
    // 循环读取k个开始时间和持续时间的对，并更新kk数组
    for (int i = 1; i <= k; i++) {
        cin >> h[i].p >> h[i].t;
        kk[h[i].p]++;
    }
    // 从后向前遍历所有位置
    for (int i = n; i >= 1; i--) {
        if (kk[i] == 0) {
            // 如果当前位置没有工作，则继承下一个位置的结果加1及休息1分钟
            dp[i] = dp[i + 1] + 1;
        } else {
            // 否则，遍历，找到最大值
            for (int j = 1; j <= k; j++) {
                if (i == h[j].p) {
                    dp[i] = max(dp[i], dp[i + h[j].t]);
                }
            }
        }
    }
    // 输出最终结果
    cout << dp[1] << endl;
    return 0;
}