D. Colored Rectangles
考虑数据范围 显然可以n3dp
我们发现dp转移时不是特别好枚举
所以我们选择记忆化搜索
打完 你们可能会发现过不去第三个样例
显然我们应该sort一遍
不然显然正解不在我们的dp范围内
而sort完之后可以感性理解一下
我们肯定要是最优解肯定是大的和大的一起
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
const int M = 998244353;
const int mod = 1e9+7;
#define int long long
int up(int a,int b){return a<0?a/b:(a+b-1)/b;}
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define YES cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
#define _ 0
#define pi acos(-1)
#define INF 0x3f3f3f3f3f3f3f3f
#define fast ios::sync_with_stdio(false);cin.tie(nullptr);
int f[210][210][210];
vector<int>R,G,B;
int dp(int x,int y,int z){
int &v=f[x][y][z];
if((!x&&!y)||(!x&&!z)||(!z&&!y))return 0;
if(v!=-1)return v;
if(x&&y)v=max(dp(x-1,y-1,z)+R[x]*G[y],v);
if(x&&z)v=max(dp(x-1,y,z-1)+R[x]*B[z],v);
if(y&&z)v=max(dp(x,y-1,z-1)+G[y]*B[z],v);
return v;
}
void solve() {
int n,m,q;cin>>n>>m>>q;
memset(f,-1,sizeof f);
R.resize(n+1),G.resize(m+1),B.resize(q+1);
for(int i=1;i<=n;i++)cin>>R[i];
for(int i=1;i<=m;i++)cin>>G[i];
for(int i=1;i<=q;i++)cin>>B[i];
sort(all(R)), sort(all(G)), sort(all(B));
cout<<dp(n,m,q)<<endl;
}
signed main(){
fast
int t;t=1;//cin>>t;
while(t--) {
solve();
}
return ~~(0^_^0);
}
标签:sort,Educational,Rated,return,int,Codeforces,&&,const,dp
From: https://www.cnblogs.com/ycllz/p/16838645.html