Codeforces 158E Phone Talks-蒲公英云

Codeforces 158E Phone Talks

http://codeforces.com/contest/158/problem/E

题目大意：

麦克是个名人每天都要接n电话，每通电话给出打来的时间和持续时间，麦克可以选择接或不接，但是只能不接k通电话。如果某通电话打来时麦克正在打电话他可以选择让电话排队，或者忽略不接。当麦克空闲时首先从排队的第一个打来的电话开始接起。麦克是个很懒的人，所以需要大量的睡觉，但是睡觉的时间必须是连续的，因此要求出麦克能睡觉的最大连续时间。

思路:dp[i][j]代表前i个电话，不听j个的最少时间，然后枚举即可

1 #include<cstdio>
 2 #include<cmath>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<iostream>
 6 struct node{
 7     int t,d;
 8 }p[200005];
 9 int n,m,f[5005][5005];
10 bool cmp(node a,node b){
11     return a.t<b.t;
12 }
13 int read(){
14     int t=0,f=1;char ch=getchar();
15     while (ch<'0'||ch>'9'){
    if (ch=='-') f=-1;ch=getchar();}
16     while ('0'<=ch&&ch<='9'){t=t*10+ch-'0';ch=getchar();}
17     return t*f;
18 }
19 int main(){    
20     n=read();m=read();
21     for (int i=0;i<n;i++) p[i].t=read(),p[i].d=read();
22     std::sort(p,p+n,cmp);
23     p[n].t=86401;
24     f[0][1]=0;
25     f[0][0]=p[0].t+p[0].d-1;
26     if (m==n){
27         printf("86400");
28         return 0;
29     }
30     for (int i=1;i<n;i++){
31         f[i][0]=std::max(p[i].t-1,f[i-1][0])+p[i].d;
32         for (int j=1;j<=m&&j<=i;j++){
33             int xx=p[i].t-1;
34             if (i-1>=j) xx=std::max(xx,f[i-1][j]);
35             f[i][j]=std::min(f[i-1][j-1],xx+p[i].d);
36         }
37     }
38     int ans=0;
39     for (int i=0;i<n;i++)
40      for (int j=0;j<=m;j++){
41             int x=std::min(n,m-j+i+1);
42             ans=std::max(ans,p[x].t-1-f[i][j]);
43      }
44     printf("%d\n",ans);
45     return 0;
46 }