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 i0;iR;i){ for(int j0;jG;j){ for(int k0;kB;k){ if(i1j1){ dp[i][j][k]max(dp[i][j][k],dp[i-1][j-1][k]r[i]*g[j]); } if(i1k1){ dp[i][j][k]max(dp[i][j][k],dp[i-1][j][k-1]r[i]*b[k]); } if(j1k1){ dp[i][j][k]max(dp[i][j][k],dp[i][j-1][k-1]g[j]*b[k]); } ansmax(ans,dp[i][j][k]); } } }完整代码(求赞)#includebits/stdc.h using namespace std; #define int long long const int N2e25; int R,G,B,ansLLONG_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 xy; } signed main(){ scanf(%lld%lld%lld,R,G,B); for(int i1;iR;i){ scanf(%lld,r[i]); } sort(r1,rR1,cmp); for(int i1;iG;i){ scanf(%lld,g[i]); } sort(g1,gG1,cmp); for(int i1;iB;i){ scanf(%lld,b[i]); } sort(b1,bB1,cmp); for(int i0;iR;i){ for(int j0;jG;j){ for(int k0;kB;k){ if(i1j1){ dp[i][j][k]max(dp[i][j][k],dp[i-1][j-1][k]r[i]*g[j]); } if(i1k1){ dp[i][j][k]max(dp[i][j][k],dp[i-1][j][k-1]r[i]*b[k]); } if(j1k1){ dp[i][j][k]max(dp[i][j][k],dp[i][j-1][k-1]g[j]*b[k]); } ansmax(ans,dp[i][j][k]); } } } printf(%lld,ans); return ~(-1); }