題目連結CF-1398D Educational Codeforces Round 93
有三種顔色,R、G、B,我們要用他們來構成矩形的長和寬,要求是矩陣的長和寬不能是同一種顔色,也就是一個矩陣必須是兩個不同顔色來構成的。并且每個顔色對應的值隻能用一次。
于是,就有貪心政策,肯定是要讓權值大的盡量和權值大的進行一個比對,這樣能保證權值大的被利用的效果最好。
于是,我們可以對每種顔色降序排序,但是現在就是該确定怎樣比對了,是以可以用一個
的這樣的一個三維dp來進行維護這個東西。
那麼很明顯的,dp方程就出來了:
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <unordered_map>
#include <unordered_set>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
#define INF 0x3f3f3f3f
#define HalF (l + r)>>1
#define lsn rt<<1
#define rsn rt<<1|1
#define Lson lsn, l, mid
#define Rson rsn, mid+1, r
#define QL Lson, ql, qr
#define QR Rson, ql, qr
#define myself rt, l, r
using namespace std;
typedef unsigned long long ull;
typedef unsigned int uit;
typedef long long ll;
int num[3];
int dp[205][205][205];
int main()
{
scanf("%d%d%d", &num[0], &num[1], &num[2]);
vector<int> col[3];
for(int i=0; i<3; i++) col[i].resize(num[i]);
for(int i=0; i<3; i++)
{
for(int j=0; j<num[i]; j++) scanf("%d", &col[i][j]);
sort(col[i].begin(), col[i].end(), greater<>{} );
}
memset(dp, 0, sizeof(dp));
int ans = 0;
for(int i=0, a, b, c; i<=num[0]; i++)
{
for(int j=0; j<=num[1]; j++)
{
for(int k=0; k<=num[2]; k++)
{
a = (j && k) ? col[1][j - 1] * col[2][k - 1] + dp[i][j - 1][k - 1] : 0;
b = (i && k) ? col[0][i - 1] * col[2][k - 1] + dp[i - 1][j][k - 1] : 0;
c = (i && j) ? col[0][i - 1] * col[1][j - 1] + dp[i - 1][j - 1][k] : 0;
dp[i][j][k] = max(a, max(b, c));
ans = max(ans, dp[i][j][k]);
}
}
}
printf("%d\n", ans);
return 0;
}