CF1398D Colored Rectangles

考虑动态规划。先将r,g,b函数从大到小排序，然后设dp[i][j][k]表示选择前i个r，前j个g，前k个b的最大值。

转移：

dp[i][j][k]=max({dp[i-1][j-1][k]+r[i]*g[j],dp[i-1][j][k-1]+r[i]*b[k],dp[i][j-1][k-1]+g[j]*b[k]});

也就是：

for(int i=0;i<=R;i++){ for(int j=0;j<=G;j++){ for(int k=0;k<=B;k++){ if(i>=1&&j>=1){ dp[i][j][k]=max(dp[i][j][k],dp[i-1][j-1][k]+r[i]*g[j]); } if(i>=1&&k>=1){ dp[i][j][k]=max(dp[i][j][k],dp[i-1][j][k-1]+r[i]*b[k]); } if(j>=1&&k>=1){ dp[i][j][k]=max(dp[i][j][k],dp[i][j-1][k-1]+g[j]*b[k]); } ans=max(ans,dp[i][j][k]); } } }

完整代码(求赞)：

#include<bits/stdc++.h> using namespace std; #define int long long const int N=2e2+5; int R,G,B,ans=LLONG_MIN,r[N],g[N],b[N],dp[N][N][N];//dp[i][j][k]表示用了前i个，前j个，前k个的最大值。 bool cmp(int x,int y){ return x>y; } signed main(){ scanf("%lld%lld%lld",&R,&G,&B); for(int i=1;i<=R;i++){ scanf("%lld",&r[i]); } sort(r+1,r+R+1,cmp); for(int i=1;i<=G;i++){ scanf("%lld",&g[i]); } sort(g+1,g+G+1,cmp); for(int i=1;i<=B;i++){ scanf("%lld",&b[i]); } sort(b+1,b+B+1,cmp); for(int i=0;i<=R;i++){ for(int j=0;j<=G;j++){ for(int k=0;k<=B;k++){ if(i>=1&&j>=1){ dp[i][j][k]=max(dp[i][j][k],dp[i-1][j-1][k]+r[i]*g[j]); } if(i>=1&&k>=1){ dp[i][j][k]=max(dp[i][j][k],dp[i-1][j][k-1]+r[i]*b[k]); } if(j>=1&&k>=1){ dp[i][j][k]=max(dp[i][j][k],dp[i][j-1][k-1]+g[j]*b[k]); } ans=max(ans,dp[i][j][k]); } } } printf("%lld",ans); return ~(-1); }