是的,有是一个DP

只是为了刷试炼场

然后呢....看了一下题目,,..感觉,,
首个思路...要排个序,按照吃饭速度排
设f[i][j][k]代表前i个人,j个人在一号,k个人在二号...然后..?

哎?那么三维就有带点累赘了哎!

然后想不出来怎么写了

#include <iostream> #include <stdio.h> #include <string.h> #include <algorithm> #define maxn 200 using namespace std ; int read() { int x = 0 , f = 1 ; char s = getchar() ; while(s > '9' || s < '0') {if(s == '-') f = -1 ; s = getchar() ;} while(s <='9' && s >='0') {x = x * 10 + (s-'0'); s = getchar() ;} return x*f ; } int n ; struct dy{ int x , y ; }a[maxn] ; int f[maxn][maxn*maxn] , sum[maxn] ; bool cmp(dy x ,dy y) { return x.y > y.y ; } int main () { n = read () ; for(int i = 1 ; i <= n ; i ++) { a[i].x = read() , a[i].y = read() ; } sort(a+1,a+1+n,cmp) ; for(int i = 1 ; i <= n ; i ++) { sum[i] = sum[i-1] + a[i].x ; } memset(f,0x3f,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].x) f[i][j] = min(f[i][j],max(f[i-1][j-a[i].x],j+a[i].y)) ; f[i][j] = min(f[i][j],max(f[i-1][j],sum[i]-j+a[i].y)) ; } } int ans = 9999999999 ; for(int i = 0 ; i <= sum[n] ; i ++) { ans = min(ans,f[n][i]) ; } printf("%d\n",ans) ; return 0 ; }