D - Colored Rectangles（动态规划）

 

给出红绿蓝三种颜色的木棍，每种长度的木棍每一次给一对，现在每次取两对木棍，组成由两种颜色组成的长方形，求最后长方形的面积之和最大是多少 

这样思路就很简单了，每次都从三个数组中挑选出最大的和次大的，模拟即可

但是你会发现，当有一种颜色的木棍数量很多时，假设 R > B+G

最优的策略还会是这样吗？

有可能存在 B G 两种颜色相互组成木棍，而我们希望让所有的 B G 都与 R 组成木棍

这两种决策需要再次比较大小，这样问题的复杂性就比较高了

WA代码： 

const int N=1e5+5;
 
    int n,m,t;
    int i,j,k;
    int a[N];
    int b[N];
    int c[N];
    
int main()
{
    //IOS;
    while(cin>>n>>m>>t){
        for(i=1;i<=n;i++) cin>>a[i];
        for(i=1;i<=m;i++) cin>>b[i];
        for(i=1;i<=t;i++) cin>>c[i];

        sort(a+1,a+1+n,greater<int>());
        sort(b+1,b+1+m,greater<int>());
        sort(c+1,c+1+t,greater<int>());
        int pa=1,pb=1,pc=1;
        ll ans=0;
        while(true){
            if(pa>n && pb>m) break;
            if(pa>n && pc>t) break;
            if(pb>m && pc>t) break;
            vector<int> v;
            v.pb(a[pa]);
            v.pb(b[pb]);
            v.pb(c[pc]);
            sort(v.begin(),v.end());
            ans+=1ll*v[2]*v[1];
            if(v[1]==a[pa] && v[2]==b[pb]) pa++,pb++;
            else if(v[1]==a[pa] && v[2]==c[pc]) pa++,pc++;
            else if(v[1]==b[pb] && v[2]==a[pa]) pb++,pa++;
            else if(v[1]==b[pb] && v[2]==c[pc]) pb++,pc++;
            else if(v[1]==c[pc] && v[2]==a[pa]) pc++,pa++;
            else if(v[1]==c[pc] && v[2]==b[pb]) pc++,pb++;
        }
        pll(ans);
    }
    //PAUSE;
    return 0;
}

AC代码：

const int N=200+5;
 
    int n,m,t;
    int i,j,k;
    int a[N];
    int b[N];
    int c[N];
    int dp[N][N][N];
    
int main()
{
    IOS;
    while(cin>>n>>m>>t){
        for(i=1;i<=n;i++) cin>>a[i];
        for(i=1;i<=m;i++) cin>>b[i];
        for(i=1;i<=t;i++) cin>>c[i];

        sort(a+1,a+1+n,greater<int>());
        sort(b+1,b+1+m,greater<int>());
        sort(c+1,c+1+t,greater<int>());

        int ans=0;
        for(i=0;i<=n;i++){
            for(j=0;j<=m;j++){
                for(k=0;k<=t;k++){
                    dp[i+1][j+1][k]=max(dp[i+1][j+1][k],dp[i][j][k]+a[i+1]*b[j+1]);
                    dp[i+1][j][k+1]=max(dp[i+1][j][k+1],dp[i][j][k]+a[i+1]*c[k+1]);
                    dp[i][j+1][k+1]=max(dp[i][j+1][k+1],dp[i][j][k]+b[j+1]*c[k+1]);
                    ans=max(ans,dp[i+1][j+1][k]);
                    ans=max(ans,dp[i+1][j][k+1]);
                    ans=max(ans,dp[i][j+1][k+1]);
                }
            }
        }
        cout<<ans<<endl;
    }
    //PAUSE;
    return 0;
}