一道很有趣的 dp 题。
这道题是以答案为下标来设定状态，在这种生产问题这个套路还是挺常见的，需要积累一下。
我们令 \(f_{i,j}\) 为前 \(i\) 个任务 \(A\) 机器花了\(j\) 时间的时候，\(B\) 机器花费的时间最少是多少。
所以答案就是 \(\min\{\max\{i,f_{n,i}\}\}\) 。我们对于每一个时间 \(i\) 所需要的总时间就是做完前 \(n\) 个任务 \(B\) 花费的时间和 \(A\) 花费的时间的最大值。由于我们枚举的 \(i\) 就是 \(A\) 花费的时间，所以只需与 \(f_{n,i}\) 取最大值即可。
转移可以考虑从三个方向转移过来，对于当前任务，我们分别考虑是 \(A\) 做，\(B\) 做，还是 \(A\) 和 \(B\) 一起做。
即可以推出转移方程。
\[f_{i,j}=\max\left\{\begin{array}{l}f_{i-1,j-t1_i}\\ f_{i-1,j}+t2_i\\ f_{i-1,j-t3_i}+t3_i \end{array}\right. \]我们发现这样的空间开销是很大的，因为我们既要记录是哪个任务还要记录时间。
我们发现对于第 \(i\) 个任务只能从 \(i-1\) 这个任务转移过来，所以可以滚动数组。
还有一个关于枚举的时间的优化。不难发现，对于当前任务 \(i\) 的时间 \(j\)，\(j\) 一定不会超过前 \(i-1\) 个任务所花的时间的最大值。
即 \(j\le \sum{\max(t1_i,t2_i,t3_i)}\) 。
细节不算多，但注意数组开大点，因为时间的大小比较玄学。
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=3e4+10;
int t1[N],t2[N],t3[N];
int n;
int dp[10][N];
signed main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>t1[i]>>t2[i]>>t3[i];
}
int sum=0;
memset(dp,0x3f,sizeof(dp));
dp[0][0]=0;
for(int i=1;i<=n;i++)
{
sum+=max(t1[i],t3[i]);
memset(dp[i&1],0x3f,sizeof(dp[i&1]));
for(int j=0;j<=sum;j++)
{
if(t2[i]!=0) dp[i&1][j]=min(dp[(i&1)^1][j]+t2[i],dp[i&1][j]);
if(t1[i]!=0 and j-t1[i]>=0) dp[i&1][j]=min(dp[i&1][j],dp[(i&1)^1][j-t1[i]]);
if(t3[i]!=0 and j-t3[i]>=0) dp[i&1][j]=min(dp[i&1][j],dp[(i&1)^1][j-t3[i]]+t3[i]);
}
}
int ans=0x7fffffff;
for(int i=0;i<=sum;i++)
{
ans=min(ans,max(i,dp[n&1][i]));
}
cout<<ans;
return 0;
}