CF1398D 【Colored Rectangles】

题目翻译

给出 (R) 对红色木棍 (r_1,r_2...r_R)，(G) 对绿色木棍 (g_1,g_2...g_G)，(B) 对蓝色木棍 (b_1,b_2...b_B) 的长度（ (R,G,B le 200) ），每次可以选出两对颜色不同的木棍组成一个矩形，每对木棍只能使用一次，木棍可以有剩余。请最大化所有组成的矩形的面积。

思路

很容易想到一个贪心的思路即在同一种颜色的木棍中，如果一对长度为 (k) 的木棍选过，那么所有长度大于 (k) 的木棍都已经选过。

那么可以先将每种颜色的木棍排降序，这样最优解所选的木棍一定是这个颜色的一个前缀。

这样的话再进行dp就很简单了，设 (dp_{i,j,k}) 为已经选了 (1sim i) 中的所有红色木棍，(1sim j) 中的所有绿色木棍，(1sim k) 中的所有蓝色木棍。

转移即：

[dp_{i+1,j+1,k}=max(dp_{i+1,j+1,k},dp_{i,j,k}+r_{i+1} imes g_{j+1}) ]

[dp_{i,j+1,k+1}=max(dp_{i,j+1,k+1},dp_{i,j,k}+g_{j+1} imes b_{k+1}) ]

[dp_{i+1,j,k+1}=max(dp_{i+1,j,k+1},dp_{i,j,k}+r_{i+1} imes b_{k+1}) ]

时间复杂度：( ext{O}(R imes G imes B))

Code

#include<bits/stdc++.h>

using namespace std;

int read()
{
	int ans=0,f=1;
	char b=getchar();
	while(b>'9'||b<'0'){if(b=='-')f=-1;b=getchar();}
	while(b>='0'&&b<='9'){ans=ans*10+b-'0';b=getchar();}
	return ans*f;
}

const int N=205;
int R,G,B,r[N],g[N],b[N],dp[N][N][N],ans;

bool cmp(int a,int b)
{
	return a>b;
}

signed main()
{
	R=read();G=read();B=read();
	for(int i=1;i<=R;++i)
		r[i]=read();
	for(int i=1;i<=G;++i)
		g[i]=read();
	for(int i=1;i<=B;++i)
		b[i]=read();
	sort(r+1,r+1+R,cmp);
	sort(g+1,g+1+G,cmp);
	sort(b+1,b+1+B,cmp);
	for(int i=0;i<=R;++i)
		for(int j=0;j<=G;++j)
			for(int k=0;k<=B;++k)
			{
				dp[i+1][j+1][k]=max(dp[i+1][j+1][k],dp[i][j][k]+r[i+1]*g[j+1]);
				dp[i][j+1][k+1]=max(dp[i][j+1][k+1],dp[i][j][k]+g[j+1]*b[k+1]);
				dp[i+1][j][k+1]=max(dp[i+1][j][k+1],dp[i][j][k]+r[i+1]*b[k+1]);
				ans=max(ans,dp[i][j][k]);
			}
	printf("%d
",ans);
	return 0;
}