链接 P2224[HNOI2001]产品加工
noip刷水题系列- \(ycb\)的套路，把答案压到状态里，设\(f_{i,j}\)表示当前在处理\(i\)个工作，\(a\)的时间为\(j\)的\(b\)时间最小值。
- 这样就不需要考虑工作的排序了，直接转移即可。
- 正确性？因为考虑工作排序的原因是某个人一直在等另外一个，但是我们可以贪心的把一起要做的工作最开始全部做掉，这样后面的决策两个人都是独立的了。
- 所以出题人为什么\(n\leq 6*10^3\)，感觉复杂度还是有点假。
#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;
}
