题意:三种木棍,分别有 R对 G对 B对两种不同木棍对可以弄移一个矩形,要求矩形面积总和最大
思路:看题面,这种几个变量互相影响并且最终目标固定的题目感觉就要用dp,而且数据比较小应该就是能用三维dp,虽然我比赛时没做出来,但是我想的挺明白的,状态转移就是dp[i][j][k]=max( dp[i-1][j-1][k]+R[i]*G[i],dp[i][j][k] )---------------------另外两个同理,每次选一个矩形
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const int N=205;
ll R,G,B;
ll r[N],g[N],b[N];
ll dp[N][N][N];int main()
{int i,j,k;cin>>R>>G>>B;for(i=1;i<=R;++i) cin>>r[i];for(i=1;i<=G;++i) cin>>g[i];for(i=1;i<=B;++i) cin>>b[i];r[0]=g[0]=b[0]=-1;sort(r+1,r+1+R);sort(g+1,g+1+G);sort(b+1,b+1+B);ll ans=0;ll x,y,z;for(i=0;i<=R;i++){for(j=0;j<=G;j++){for(k=0;k<=B;k++){if(i>0&&j>0) x=dp[i-1][j-1][k]+r[i]*g[j];if(j>0&&k>0) y=dp[i][j-1][k-1]+g[j]*b[k];if(i>0&&k>0) z=dp[i-1][j][k-1]+r[i]*b[k];dp[i][j][k]=max(max(x,y),z);}}}cout<<dp[R][G][B]<<"\n";return 0;
}