比较水的DP
但是比较难想
整体思路还是很好理解的
在洛谷的题解里有一个一维的
> 什么时候去看一下
下面发我的代码
#include<bits/stdc++.h> #define max(a,b) (a>b?a:b) #define min(a,b) (a<b?a:b) using namespace std; #define N 205 int f[N][N*N];//f[前i个人][结束时间] int sum[N]; struct data { int a, b;//a打饭 b吃饭 bool operator <(const data &now) const { return b>now.b; } }a[N]; //吃饭慢的先吃 吃饭快的后吃 //然后再DP 选1，2窗口(两种状态) int main() { int n,ans=0x7fffffff; scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d%d", &a[i].a, &a[i].b); sort(a + 1, a + 1 + n); for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + a[i].a; memset(f, 127, sizeof(f)); f[0][0] = 0; for (int i = 1; i <= n; i++)//枚举人数 { for (int j = 0; j <= sum[i]; j++) { if(j>=a[i].a) f[i][j]=min(max(f[i-1][j-a[i].a],j+a[i].b),f[i][j]); f[i][j]=min(f[i][j],max(f[i-1][j],sum[i]-j+a[i].b)); } } for(int i=0;i<=sum[n];i++)ans = min(ans, f[n][i]); printf("%d", ans); return 0; }
转载于:https://www.cnblogs.com/lincold/p/9898075.html
相关资源：JAVA上百实例源码以及开源项目