Codeforces 1398 D. Colored Rectangles（dp）

传送门

题意：

每次可以选不同颜色的数字相乘，求最大值

思路：

开始写的贪心一直wa7。。。
正解：dp
$dp[i][j][k]$表示当前每种颜色选的个数
当然为了使结果最大，三个数组都要从大到小排序
$dp[i][j][k]$的下一个状态有三种情况
$dp[i+1][j+1][k]$//选RG
$dp[i+1][j][k+1]$//选RB
$dp[i][j+1][k+1]$//选GB
最后取个最大值即可

代码：

int r[650],g[650],b[650];
int R,G,B;
int cmp(int a,int b){return a>b;
}
ll dp[250][250][250];
int main()
{std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>R>>G>>B;rep(i,1,R)cin>>r[i];rep(i,1,G)cin>>g[i];rep(i,1,B)cin>>b[i];sort(r+1,r+R+1,cmp);sort(g+1,g+G+1,cmp);sort(b+1,b+B+1,cmp);ll ans=0;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+1][j][k+1]=max(dp[i+1][j][k+1],dp[i][j][k]+r[i+1]*b[k+1]);dp[i][j+1][k+1]=max(dp[i][j+1][k+1],dp[i][j][k]+g[j+1]*b[k+1]);}for(int i=0;i<=R;i++)for(int j=0;j<=G;j++)for(int k=0;k<=B;k++)ans=max(ans,dp[i][j][k]);cout<<ans<<endl;return 0;
}