D. Colored Rectangles

제목: 세 가지 색깔을 주고 한 쌍으로 나뭇가지가 나타나는데 길이는 각각 ai, bi, ciai、b_i、c_iai,bi,ci, 모든 구성된 직사각형의 면적과 최대가 얼마냐고 묻는다.(각 직사각형은 반드시 두 가지 색깔이 있어야 한다. 각 색깔의 나무 줄기 수는 200을 넘지 않는다) 사고방식: 우선 욕심만 부리는 것은 옳지 않다. 우리가 원하는 것은 모든 직사각형의 면적과 최대이기 때문에 매번 선택할 때 가장 긴 두 쌍의 가장자리만 선택할 수 없고 각 색깔의 나무 줄기의 수량에 근거해야 한다.그래서 우리는 폭력적으로 모든 상황을 찾아내서 최대치를 찾아낼 수밖에 없다.O(n3)dp[i][j][k]dp[i][j][k]dp[i][j][k]는 각 색깔의 나무 줄기에서 선택한 개수를 대표한다.

#include
using namespace std;
typedef long long LL;
const int N = 210;

int dp[N][N][N];
int a[N],b[N],c[N];

bool cmp(int x,int y){
	return x>y;
}

int main()
{
	int x,y,z;
	cin>>x>>y>>z;
	for(int i=1;i<=x;i++) cin>>a[i];
	for(int i=1;i<=y;i++) cin>>b[i];
	for(int i=1;i<=z;i++) cin>>c[i];
	
	sort(a+1,a+x+1,cmp);
	sort(b+1,b+y+1,cmp);
	sort(c+1,c+z+1,cmp);
	int ans=0;
	
	for(int i=0;i<=x;i++)
	for(int j=0;j<=y;j++)
	for(int k=0;k<=z;k++){
		if(i&&j) dp[i][j][k] = max(dp[i][j][k],dp[i-1][j-1][k]+a[i]*b[j]);
		if(i&&k) dp[i][j][k] = max(dp[i][j][k],dp[i-1][j][k-1]+a[i]*c[k]);
		if(j&&k) dp[i][j][k] = max(dp[i][j][k],dp[i][j-1][k-1]+b[j]*c[k]);
		ans = max(ans,dp[i][j][k]);
	}
	cout<<ans<<"
";
	return 0;
}