bzoj 1899 贪心+dp

思路：这个贪心排顺序我居然没看出来。 吃饭时间长的在前面， 用反证法很容易得出。 剩下的就是瞎dp啦。

#include<bits/stdc++.h>
#define LL long long
#define fi first
#define se second
#define mk make_pair
#define PII pair<int, int>
#define PLI pair<LL, int>
#define ull unsigned long long
using namespace std;const int N = 200 + 7;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;PII a[N];
int dp[2][N*N*2], cur, n;int main() {scanf("%d", &n);for(int i = 1; i <= n; i++) scanf("%d%d", &a[i].se, &a[i].fi);sort(a + 1, a + 1 + n);reverse(a + 1, a + 1 + n);memset(dp[cur], inf, sizeof(dp[cur]));dp[cur][0] = 0;int sum = 0;for(int i = 1; i <= n; i++) {cur ^= 1;memset(dp[cur], inf, sizeof(dp[cur]));for(int j = 0; j < N*N*2; j++) {if(dp[cur^1][j] == inf) continue;dp[cur][j+a[i].se] = min(dp[cur][j+a[i].se], max(dp[cur^1][j], j+a[i].fi+a[i].se));dp[cur][j] = min(dp[cur][j], max(dp[cur^1][j], (sum-j)+a[i].fi+a[i].se));}sum += a[i].se;}int ans = inf;for(int i = 0; i < N*N*2; i++)ans = min(ans, dp[cur][i]);printf("%d\n", ans);return 0;
}/*
*/