首页 > 其他分享 >Educational Codeforces Round 93 (Rated for Div. 2) D

Educational Codeforces Round 93 (Rated for Div. 2) D

时间:2022-10-29 14:22:19浏览次数:59  
标签:sort Educational Rated return int Codeforces && const dp

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

相关文章

  • Codeforces Round #827 (Div. 4) A-G
    比赛链接A题解知识点:模拟。时间复杂度\(O(1)\)空间复杂度\(O(1)\)代码#include<bits/stdc++.h>#definelllonglongusingnamespacestd;boolsolve(){......
  • Educational Codeforces Round 1
    EducationalCodeforcesRound1C.Nearestvectors题目大意给出n个向量,求出其中夹角最小的两个向量。分析求出所有向量与x轴的夹角,然后排序,两两比较夹角。AC_code#......
  • Codeforces Round #826 (Div. 3) A-E
    比赛链接A题解知识点:模拟。时间复杂度\(O(n)\)空间复杂度\(O(n)\)代码#include<bits/stdc++.h>#definelllonglongusingnamespacestd;boolsolve(){......
  • Codeforces Round #830 (Div. 2)(持续更新)
    PrefaceAB很水,C一般难度,D1很简单但D2确实巧妙没有现场打有点可惜,后面补的时候都是1A(结果每次比赛的时候都要莫名WA上好久)A.Bestie我刚开始没咋想,感觉操作步数不会很......
  • Codeforces Round #739 (Div. 3) E
    E.PolycarpandStringTransformation显然我们可以通过看谁消失的最早知道删除序列然后有了删除序列以后我们能干什么呢显然对于每一个删除序列我们要是第一次就把......
  • Codeforces Round #672 (Div. 2) D
    D.RescueNibel!转化题意就是叫我们求k条线段都有重合的方案数最开始想的是离散化+线段树手模拟一下样例这样会是有重复的我们要如何保证不重不漏!显然我们可以将线......
  • Codeforces Round #631 (Div. 1) - Thanks, Denis aramis Shitov! A
    A.DreamoonLikesColoring显然我们不看把整块涂满最优的构造就是1234....但是要考虑将整块板涂满我们就要往右挪显然我们每次挪后面的板子都会动我们一定要让......
  • Educational Codeforces Round 138 F Distance to the Path
    DistancetothePath思维+树链剖分首先与树链剖分无关,先考虑如果只更新一个点的情况因为更新一个点,它既能向根的方向更新,又能向子树方向更新,非常难维护,于是我们只......
  • 近期 educational 题目收集
    最近对我比较有启发意义的题。可能很简单但是我都不会/pxARC108E(概率、区间DP)2022.10.16多校联考T4(树的直径、容斥、点分治、NTT)P3239(容斥、概率、DP)2022.10.22联......
  • Codeforces Round #829 (Div. 2)-C1
    C1题目链接:https://codeforces.com/contest/1754/problem/C1emmm,不知道怎么说,做的时候考虑的问题是我通过什么方法来划分整个数组使得题意成立,后面又困在怎么判断是否存......