上古时期的 T5 难度确实比现在要简单不少。

很有限的资源，分配时间使用，就很动态规划。

首先有一个观察，虽然有四种策略，但是每种都用到了 CPU，那么使用两块 CPU 和使用两块 CPU + 一块 GPU 是不可能共存的，那么其实我们的可以将这两者合并起来，取其最小值即可。这样就只有三种策略了。

算法1

设 $f[i,j,k,l]$ 表示完成前 $i$ 个任务，CPU1 使用 $i$ 个单位时间，CPU2 使用 $j$ 个单位时间，GPU 使用 $k$ 个单位时间是否可行，也就是说这是一个 bool 类型的数组。答案即为：

$$\min_{j=1\sim nm,k=1\sim nm,l=1\sim nm,f[n,j,k,l]=1}\max(j,k,l) $$

状态转移方程是比较显然的：

$$ f[i,j,k,l]=(f[i,j-a[i],k,l],f[i-1,j,k-a[i],l],f[i-1,j-b[i],k-b[i],l-b[i]),\\f[i-1,j-c[i],k,l-c[i]],f[i-1,j,k-c[i],l-c[i]]); $$

第一维大小为 $n$，第二、三、四维大小为最大消耗时间，实际值不超过 $\frac{nm}{2}$，时间复杂度 $O(n^4m^3)$ 带一个 $\frac{1}{8}$ 的常数，没有这个真过不了（逃）。

空间复杂度 $O(n^4m^3)$，显然是无法通过的，滚动数组一下是 $O(n^3m^3)$就可以通过了。

代码如下：

#include<bits/stdc++.h>
using namespace std;
int n,m,a[50],b[50],c[50],d[50],e[50];
bool f[2][210][210][210];
int main() {
	scanf("%d",&n);
	int A=0;
	for(int i=1;i<=n;i++) {
		scanf("%d%d%d%d",&a[i],&b[i],&c[i],&d[i]);
		b[i]=min(b[i],d[i]);
		e[i]=a[i];A+=a[i];
	}
	sort(e+1,e+n+1);
	for(int i=2;i<=n;i+=2) m+=e[i];
	m=max(m,A-m);
	f[0][0][0][0]=1;
	for(int i=1;i<=n;i++) {
		int ii=i&1;
		for(int j=0;j<=m;j++) {
			for(int k=0;k<=m;k++) {
				for(int l=0;l<=m;l++) {
					f[ii][j][k][l]=0;
					if(j>=a[i])	f[ii][j][k][l]|=f[ii^1][j-a[i]][k][l];
					if(k>=a[i])	f[ii][j][k][l]|=f[ii^1][j][k-a[i]][l];
					if(j>=b[i]&&k>=b[i]&&l>=b[i]) f[ii][j][k][l]|=f[ii^1][j-b[i]][k-b[i]][l-b[i]];
					if(l>=c[i]) {
						if(j>=c[i]) f[ii][j][k][l]|=f[ii^1][j-c[i]][k][l-c[i]];
						if(k>=c[i]) f[ii][j][k][l]|=f[ii^1][j][k-c[i]][l-c[i]];
					}
				}
			}
		}
	}
	int ans=m;
	for(int j=0;j<=m;j++) for(int k=0;k<=m;k++) for(int l=0;l<=m;l++)
		if(f[n&1][j][k][l]) ans=min(ans,max(j,max(k,l)));
	printf("%d\n",ans);
	return 0;
}

然而我们可以敏锐地发现，这个动态规划的值是可行性0/1，那么如果我们把一维状态放在要DP的值呢？

算法2

设 $f[i,j,k]$ 表示完成前 $i$ 个任务，CPU1 使用 $i$ 个单位时间，CPU2 使用 $j$ 个单位时间的情况下，GPU 需要使用的最短时间，那么答案即为：

$$\min_{j=1\sim nm,k=1\sim nm} \max(j,k,f[n,j,k])$$

第一维大小为 $n$，第二、三维大小为最大消耗时间，实际值不超过 $\frac{nm}{2}$，时间复杂度 $O(n^3m^2)$ 带一个 $\frac{1}{4}$ 的常数，没有这个也能过。

空间复杂度 $O(n^3m^2)$，显然是无法通过的，是否滚动都能通过。

代码如下：

#include<bits/stdc++.h>
using namespace std;
int n,m,a[50],b[50],c[50],d[50],e[50];
int f[2][210][210];
int main() {
	scanf("%d",&n);
	int A=0;
	for(int i=1;i<=n;i++) {
		scanf("%d%d%d%d",&a[i],&b[i],&c[i],&d[i]);
		b[i]=min(b[i],d[i]);
		e[i]=a[i];A+=a[i];
	}
	sort(e+1,e+n+1);
	for(int i=2;i<=n;i+=2) m+=e[i];
	m=max(m,A-m);
	memset(f,0x3f,sizeof f);
	f[0][0][0]=0;
	for(int i=1;i<=n;i++) {
		int ii=i&1;
		for(int j=0;j<=m;j++) {
			for(int k=0;k<=m;k++) {
				f[ii][j][k]=1e9;
				if(j>=a[i]) f[ii][j][k]=min(f[ii^1][j-a[i]][k],f[ii][j][k]);
				if(k>=a[i]) f[ii][j][k]=min(f[ii^1][j][k-a[i]],f[ii][j][k]);
				if(j>=b[i]&&k>=b[i]) f[ii][j][k]=min(f[ii^1][j-b[i]][k-b[i]]+b[i],f[ii][j][k]);
				if(j>=c[i]) f[ii][j][k]=min(f[ii^1][j-c[i]][k]+c[i],f[ii][j][k]);
				if(k>=c[i]) f[ii][j][k]=min(f[ii^1][j][k-c[i]]+c[i],f[ii][j][k]);
			}
		}
	}
	int ans=m;
	for(int j=0;j<=m;j++) for(int k=0;k<=m;k++)
		ans=min(ans,max(f[n&1][j][k],max(j,k)));
	printf("%d\n",ans);
	return 0;
}