一上來看完題目，這很貪心，馬上寫了發貪心，wa7！
hack樣例，當面臨選擇的數有兩個相同，然後選擇了某一個，可能後序的操作，得到的值不如選另一個數的價值大。
1 2 2
100
90 90
90 30
1 2 2
100
90 30
90 90
是以正解該是dp，記錄了每個狀态的最優解。
很容易想到狀态 d p [ i ] [ j ] [ z ] dp[i][j][z] dp[i][j][z] 表示分别選擇了 i , j , z i,j,z i,j,z 個棍子的最大價值。
然後轉移的話可以從 d p [ i − 1 ] [ j − 1 ] [ z ] , d p [ i − 1 ] [ j ] [ z − 1 ] ， d p [ i ] [ j − 1 ] [ z − 1 ] dp[i-1][j-1][z],dp[i-1][j][z-1]，dp[i][j-1][z-1] dp[i−1][j−1][z],dp[i−1][j][z−1]，dp[i][j−1][z−1] 三個狀态轉移過來。
轉移方程：
dp[i][j][z] = max(dp[i][j][z],dp[i-1][j-1][z]+a[i]*b[j]);
dp[i][j][z] = max(dp[i][j][z],dp[i-1][j][z-1]+a[i]*c[z]);
dp[i][j][z] = max(dp[i][j][z],dp[i][j-1][z-1]+b[j]*c[z]);
對每組給定的數從大到小排個序，然後選擇。
參考代碼
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
const int man = 2e5+10;
#define IOS ios::sync_with_stdio(0)
#define ull unsigned ll
#define uint unsigned
#define pai pair<int,int>
#define pal pair<ll,ll>
#define IT iterator
#define pb push_back
#define fi first
#define se second
#define For(i,j,k) for (int i=(int)(j);i<=(int)(k);++i)
#define Rep(i,j,k) for (int i=(int)(j);i>=(int)(k);--i)
#define endl '\n'
#define ll long long
const ll mod = 1e9+7;
int a[man],b[man],c[man];
ll dp[205][205][205];
signed main() {
#ifndef ONLINE_JUDGE
//freopen("in.txt", "r", stdin);
//freopen("out.txt","w",stdout);
#endif
int n,m,k;cin >>n>>m>>k;
for(int i = 1;i <= n;++i)cin >> a[i];
for(int i = 1;i <= m;++i)cin >> b[i];
for(int i = 1;i <= k;++i)cin >> c[i];
sort(a+1,a+1+n,[](const int a,const int b){return a>b;});
sort(b+1,b+1+m,[](const int a,const int b){return a>b;});
sort(c+1,c+1+k,[](const int a,const int b){return a>b;});
ll ans = 0;
for(int i = 0;i <= n;++i){
for(int j = 0;j <= m;++j){
for(int z = 0;z <= k;++z){
if(i>=1&&j>=1)dp[i][j][z] = max(dp[i][j][z],dp[i-1][j-1][z]+a[i]*b[j]);
if(i>=1&&z>=1)dp[i][j][z] = max(dp[i][j][z],dp[i-1][j][z-1]+a[i]*c[z]);
if(j>=1&&z>=1)dp[i][j][z] = max(dp[i][j][z],dp[i][j-1][z-1]+b[j]*c[z]);
ans = max(ans,dp[i][j][z]);
}
}
}
cout<<ans<<endl;
return 0;
}
/*
1 2 2
100
90 90
90 30
1 2 2
100
90 30
90 90
*/