#include<bits/stdc++.h>
#define R register int
using namespace std;
const int N=6001;
int n,ans,a[N],b[N],c[N],tot[N],f[2][N*10];
int gi(){
R x=0,k=1;char c=getchar();
while(c!=‘-‘&&(c<‘0‘||c>‘9‘))c=getchar();
if(c==‘-‘)k=-1,c=getchar();
while(c>=‘0‘&&c<=‘9‘)x=(x<<3)+(x<<1)+c-‘0‘,c=getchar();
return x*k;
}
int main(){
n=gi(),ans=1e9;
for(R i=1;i<=n;++i){
a[i]=gi(),b[i]=gi(),c[i]=gi();
tot[i]=tot[i-1]+max(a[i],max(b[i],c[i]));
}
R now=0,pre=1;memset(f,0x7f,sizeof(f));
f[now][0]=0;
for(R i=1;i<=n;++i){
now^=1,pre^=1;
memset(f[now],0x7f,sizeof(f[now]));
for(R j=0;j<=tot[i];++j){
if(j>=a[i]&&a[i])f[now][j]=min(f[pre][j-a[i]],f[now][j]);
if(b[i])f[now][j]=min(f[now][j],f[pre][j]+b[i]);
if(j>=c[i]&&c[i])f[now][j]=min(f[pre][j-c[i]]+c[i],f[now][j]);
}
}
for(R i=0;i<=tot[n];++i)
ans=min(ans,max(i,f[now][i]));
cout<<ans<<endl;
return 0;
}
原文:https://www.cnblogs.com/Tyher/p/9898234.html