尼克的任务 dp 洛谷1280

　　蒟蒻表示老久没看过dp题目了，，挺水的一道dp题目都没想出来，，，

　　首先设dp[i]表示从开始到i时间的最大空闲时间，用vector to[x] 表示从x点开始的任务结束时间，cnt[x]表示从x开始的任务个数，初始化dp[i] i = 1 -> n 为 -1， dp[0]为0

　　转移时，对于dp[i]，如果dp[i-1] 为 -1，无法完成转移

　　如果dp[i-1] > 0分两种情况

　　1、如果i时刻无任务，直接dp[i] = max{dp[i], dp[i-1] + 1}

　　2、如果i时刻有任务，枚举任务，使dp[to[i][j]] = max{dp[to[i][i]]，dp[i-1]}

　　输出dp[n]即为结果

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <vector>

 const int maxn =  + ;

 int n, k;

 std :: vector <int> to[maxn];

 int dp[maxn], cnt[maxn];

 int tx, ty;

 int main () {

     scanf("%d %d", &n, &k);

     for (int i = ; i <= k; i++) {

         scanf("%d %d", &tx, &ty);

         to[tx].push_back(tx + ty - );

         cnt[tx]++;

     }

     for (int i = ; i <= n; i++) dp[i] = -;

     dp[] = ;

     for (int i = ; i <= n; i++) {

         if (dp[i-] >= ) {

             if (cnt[i] > ) {

                 for (int j = ; j < to[i].size(); j++)

                     dp[to[i][j]] = std :: max(dp[to[i][j]], dp[i-]);

             } else {

                 dp[i] = std :: max(dp[i], dp[i-] + );

             }

         }

     }

     printf("%d", dp[n]);

     return ;

 }

巴特西

尼克的任务 dp 洛谷1280

最新文章

热门文章