Codeforces 1398 D. Colored Rectangles（dp）

传送门

题意：

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

思路：

开始写的贪心一直wa7。。。
正解：dp
$dp[i][j][k]$dp[i][j][k]表示当前每种颜色选的个数
当然为了使结果最大，三个数组都要从大到小排序
$dp[i][j][k]$dp[i][j][k]的下一个状态有三种情况
$dp[i+1][j+1][k]$dp[i+1][j+1][k]//选RG
$dp[i+1][j][k+1]$dp[i+1][j][k+1]//选RB
$dp[i][j+1][k+1]$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;
}