题意：给你一个通话时刻表，每个通话要么放弃要么打完，你最多可以放弃k个电话。通话过程中进来的电话可以先放到一边 。给你 n个电话打进来的时间和通话长度 ，问你最长的空闲时间是多少。
解题思路：dp[i][j]到了第i个电话 放弃了j个通话的最早的结束时间。
解题代码：
1 // File Name: 158e.cpp 2 // Author: darkdream 3 // Created Time: 2015年03月24日 星期二 16时35分24秒 4 5 #include<vector> 6 #include<list> 7 #include<map> 8 #include<set> 9 #include<deque> 10 #include<stack> 11 #include<bitset> 12 #include<algorithm> 13 #include<functional> 14 #include<numeric> 15 #include<utility> 16 #include<sstream> 17 #include<iostream> 18 #include<iomanip> 19 #include<cstdio> 20 #include<cmath> 21 #include<cstdlib> 22 #include<cstring> 23 #include<ctime> 24 #define LL long long 25 26 using namespace std; 27 struct work{ 28 int si ,di; 29 }works[5000]; 30 int dp[5000][5000]; 31 int n , k ; 32 int main(){ 33 scanf("%d %d",&n,&k); 34 int tx, ty; 35 int mx = 0 ; 36 for(int i = 1;i <= n;i ++) 37 { 38 scanf("%d %d",&tx,&ty); 39 for(int j = 0 ;j <= k ;j ++) 40 dp[i][j] = 1e9; 41 for(int j = 0 ;j <= k ;j ++) 42 { 43 if(dp[i-1][j] <= tx ) 44 { 45 mx = max(tx - dp[i-1][j]-1,mx); 46 dp[i][j] =min(tx + ty-1,dp[i][j]); 47 }else{ 48 dp[i][j] =min(dp[i-1][j] + ty,dp[i][j]); 49 } 50 dp[i][j+1] = min(dp[i][j+1],dp[i-1][j]); 51 //printf("%d ",dp[i][j]); 52 } 53 //printf(" "); 54 } 55 // printf("%d ",dp[4][1]); 56 mx = max(86400 - dp[n][k],mx); 57 printf("%d ",mx); 58 return 0; 59 }