題目描述：

分析：

乍一看我還以為是貪心！
貓 想想感覺沒問題
但是局部最優(yōu)并不能保證全局最優(yōu)
比如這組數(shù)據(jù)

19 19 19 19
20 20
20 20

如果按照貪心的做法，答案是20*20*2
但是其實答案是19*20*4

因此這道題用貪心是不對的

于是我們考慮dp
可以觀察到這道題的n非常小只有200
這就暗示我們這道題可以用$n^3$的做法去解決

那么我們就可以這樣設(shè)dp狀態(tài)
$f[i][j][k]表示用三個顏色分別用了前i,j,k個數(shù)，所能獲得的最大價值$
如何轉(zhuǎn)移呢？
考慮一次可以取兩個數(shù)
也就是說可以取12,23,13
那么分別從這三種狀態(tài)轉(zhuǎn)移過來即可

有的時候記憶化搜索比dp更好寫！

Code

#include<bits/stdc++.h>
using namespace std;const int N = 210;
int r,g,bb;
int a[N],b[N],c[N];
int f[N][N][N];bool cmp(int x,int y){return x>y;
}int Dfs(int x,int y,int z){if (f[x][y][z]) return f[x][y][z];int Max = 0;if (x && y) Max = max(Max,Dfs(x-1,y-1,z)+a[x]*b[y]);if (x && z) Max = max(Max,Dfs(x-1,y,z-1)+a[x]*c[z]);if (z && y) Max = max(Max,Dfs(x,y-1,z-1)+b[y]*c[z]);return f[x][y][z] = Max;
}int main(){cin>>r>>g>>bb;for (int i = 1; i <= r; i++) cin>>a[i];for (int i = 1; i <= g; i++) cin>>b[i];for  (int i = 1; i <= bb; i++) cin>>c[i];sort(a+1,a+r+1);sort(b+1,b+g+1);sort(c+1,c+bb+1);cout<<Dfs(r,g,bb)<<endl;return 0;
}