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

admin管理员组

文章数量:1584341

传送门

昨天写的时候直接找每一个矩阵的最大值，然后相加在一起，
然后就
Wrong answer on test 7

wa代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define inf 1e9+7
#define debug(x) cerr << #x << " = " << x << '\n'
#define LL long long
#define N 2020000

int a,b,c;
int za[N], zb[N], zc[N];

bool cmp(const int &a,const int &b){
    return a > b;
}

int main(){
      int z,x,v;
      int l;
        long long all = 0;
        scanf("%d%d%d", &a, &b, &c);
        for(int i = 0;i < a;i ++)
            scanf("%d",&za[i]);
        for(int i = 0;i < b;i ++)
            scanf("%d",&zb[i]);
        for(int i = 0;i < c;i ++)
            scanf("%d",&zc[i]);

        int i = 0, j = 0, k = 0;

        sort(za,za+a,cmp);
        sort(zb,zb+b,cmp);
        sort(zc,zc+c,cmp);
        
        while(1){
            z = za[i];
            x = zb[j];
            v = zc[k];

            if(z >= x && v >= x){
                all += z*v;
                i ++;
                k ++;
            }
            else if(x >= v && z >= v){
                all += x*z;
                i ++;
                j ++;
            }
            else{
                all += x*v;
                j ++;
                k ++;
            }
            int l = 0;
            if(i == a)
                l ++;
            if(j == b)
                l ++;
            if(k == c)
                l ++;
            if(l == 2 || l == 3)
                break;
        }
        printf("%lld\n",all);
    return 0;
}

今天看了发现是三维dp，昨天最后就剩20分钟，想的不全，就直接打代码了，还是得想明白再写，否则写的也没用

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define inf 1e9+7
#define debug(x) cerr << #x << " = " << x << '\n'
#define LL long long
#define N 202

int a,b,c;
int za[N], zb[N], zc[N];

bool cmp(const int &a,const int &b){
    return a > b;
}

int dp[N][N][N];

int main(){
    int l;
    int all = 0;
    scanf("%d%d%d", &a, &b, &c);
    for(int i = 1;i <= a;i ++)
        scanf("%d",&za[i]);
    for(int i = 1;i <= b;i ++)
        scanf("%d",&zb[i]);
    for(int i = 1;i <= c;i ++)
        scanf("%d",&zc[i]);

    sort(za+1,za+a+1,cmp);
    sort(zb+1,zb+b+1,cmp);
    sort(zc+1,zc+c+1,cmp);
 //   za[0] = zb[0] = zc[0] = -1;
    int x,y,z;

    for(int i = 0;i <= a;i ++){
        for(int j = 0;j <= b;j ++){
            for(int k = 0;k <= c;k ++){
    //    cout << "---------------------------" << endl;
                x = y = z = 0;

                if(i && j)
                    x = dp[i-1][j-1][k] + za[i] * zb[j];

                if(j && k)
                    y = dp[i][j-1][k-1] + zb[j] * zc[k];

                if(i && k)
                    z = dp[i-1][j][k-1] + za[i] * zc[k];

                dp[i][j][k] = max(max(x,y),z);
                all = max(all, dp[i][j][k]);
             //       debug (all);
            }
        }
    }
    printf("%d\n",all);
    return 0;
}

发现dp不加sort就会wa，因为并不是所有的边都会用到，边是挑大的用，这样的话就会有剩余的同色的边无法组成矩形，就得进行排序先用大的，然后用小的。

该dp操作的意思是从没有一个矩形的地方开始添加矩形（两对不同颜色的边），最后进行 n^3 的操作后全部的矩形添加最优方案以及完毕了。

sort不管是升序还是降序都ac了，可能是因为升序和降序都是有序的，只是方向相反而已，两种都是进行了全部的最优方案，所以答案不变。

本文标签： codeforcesEducationalDivRated