codeforces E. Phone Talks（dp）

题目链接：http://codeforces.com/contest/158/problem/E

题意：给出一些电话，有打进来的时间和持续的时间，如果人在打电话，那么新打进来的电话入队，如果人没有打电话，那么人必须立即接电话，或者选择一次放弃的机会，问这个最多有多长的连续的空闲的时间。

题解：按照套路最长一般都是依靠dp来求解或者贪心。然后由于数据也就4000所以不难想到设

dp[i][j]表示处理到第i个电话时，无视了j个电话之后最短的结束时间，于是转移方程如下：

dp[i][j] = min(dp[i - 1][j - 1] , max(dp[i - 1][j] , t[i] - 1) + d[i]);要么就无视当前电话，

要么接听当前电话。

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int M = 4e3 + 10;
int t[M] , d[M] , dp[M][M];
int main() {
    int n , k;
    scanf("%d%d" , &n , &k);
    for(int i = 1 ; i <= n ; i++) {
        scanf("%d%d" , &t[i] , &d[i]);
    }
    dp[0][0] = 0;
    for(int i = 1 ; i <= n ; i++) {
        dp[i][0] = max(t[i] - 1 , dp[i - 1][0]) + d[i];
        for(int j = 1 ; j <= k && j <= i ; j++) {
            dp[i][j] = min(dp[i - 1][j - 1] , max(dp[i - 1][j] , t[i] - 1) + d[i]);
        }
    }
    int ans = t[1] - 1;
    for(int i = 1 ; i <= n ; i++) {
        for(int j = 0 ; j <= k && j < i ; j++) {
            ans = max(ans , t[i] - dp[i - 1][j] - 1);
        }
    }
    for(int j = 0 ; j <= k ; j++) {
        ans = max(ans , 86400 - dp[n][j]);
    }
    printf("%d
" , ans);
    return 0;
}

codeforces E. Phone Talks（dp）

相关推荐