欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Codeforces 1398 D. Colored Rectangles(dp)

程序员文章站 2022-06-03 18:32:27
...

传送门

题意:

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;
}
相关标签: DP Codeforces