是的,有是一个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
",ans) ;
return 0 ;
}