Editorial for Trò chơi với bảng số


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

#include <iostream>
#include <algorithm>
#include <vector>
#define oo 1000000
using namespace std;

int A,B,n,f[2][202][202],a[202],b[202];

int main()
{
    int x,z=0,ans=-oo;
    cin >> n;
    for (int i=0;i<n;i++) 
    {
        cin >> x;
        if (x) a[++A]=x;
    }
    for (int i=0;i<n;i++)
    {
        cin >> x;
        if (x) b[++B]=x;
    }
    for (int i=1;i<=max(A,B);i++)
    {
        z^=1;
        for (int j=0;j<=A;j++)
            for (int k=0;k<=B;k++)
            {
                f[z][j][k]=-oo;
                if (j) f[z][j][k]=max(f[z][j][k],f[z][j-1][k]);
                if (k) f[z][j][k]=max(f[z][j][k],f[z][j][k-1]);
                if (j && k) f[z][j][k]=max(f[z][j][k],f[1-z][j-1][k-1]+a[j]*b[k]);
                if (i>=A+B-n) ans=max(ans,f[z][j][k]);
            }
    }
    cout << ans << endl;
}

Code mẫu của ladpro98

#include <iostream>
#include <cstdio>
#include <algorithm>
#define REP(i, a, b) for(int i = (a); i <= (b); i++)

const int MAXN = 202;

using namespace std;

bool was[MAXN][MAXN][MAXN];
int f[MAXN][MAXN][MAXN];
int N, m, n;
int a[MAXN], b[MAXN];

void maxi(int &a, int b) {a = a > b ? a : b;}

int dp(int i, int j, int k) {
    if (was[i][j][k]) return f[i][j][k];
    was[i][j][k] = 1;
    if (i == 0 || i < j || i < k) return 0;
    f[i][j][k] = dp(i - 1, j, k) + a[i - j] * b[i - k];
    if (j && k) maxi(f[i][j][k], dp(i - 1, j - 1, k - 1));
    if (j) maxi(f[i][j][k], dp(i - 1, j - 1, k));
    if (k) maxi(f[i][j][k], dp(i - 1, j, k - 1));
    return f[i][j][k];
}

int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> N;
    int x, cntZeroA = 0, cntZeroB = 0;
    REP(i, 1, N) {
        cin >> x;
        if (x) a[++m] = x;
        else cntZeroA++;
    }
    REP(i, 1, N) {
        cin >> x;
        if (x) b[++n] = x;
        else cntZeroB++;
    }
    cout << dp(N, cntZeroA, cntZeroB);
}

Code mẫu của RR

#include <sstream>
#include <iomanip>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <string>
#include <deque>
#include <complex>

#define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++)
#define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--)
#define REP(i,a) for(int i=0,_a=(a); i<_a; i++)
#define FORN(i,a,b) for(int i=(a),_b=(b);i<_b;i++)
#define DOWN(i,a,b) for(int i=a,_b=(b);i>=_b;i--)
#define SET(a,v) memset(a,v,sizeof(a))
#define sqr(x) ((x)*(x))
#define ll long long
#define F first
#define S second
#define PB push_back
#define MP make_pair

#define DEBUG(x) cout << #x << " = "; cout << x << endl;
#define PR(a,n) cout << #a << " = "; FOR(_,1,n) cout << a[_] << ' '; cout << endl;
#define PR0(a,n) cout << #a << " = "; REP(_,n) cout << a[_] << ' '; cout << endl;
using namespace std;

//Buffer reading
int INP,AM,REACHEOF;
#define BUFSIZE (1<<12)
char BUF[BUFSIZE+1], *inp=BUF;
#define GETCHAR(INP) { \
    if(!*inp) { \
        if (REACHEOF) return 0;\
        memset(BUF,0,sizeof BUF);\
        int inpzzz = fread(BUF,1,BUFSIZE,stdin);\
        if (inpzzz != BUFSIZE) REACHEOF = true;\
        inp=BUF; \
    } \
    INP=*inp++; \
}
#define DIG(a) (((a)>='0')&&((a)<='9'))
#define GN(j) { \
    AM=0;\
    GETCHAR(INP); while(!DIG(INP) && INP!='-') GETCHAR(INP);\
    if (INP=='-') {AM=1;GETCHAR(INP);} \
    j=INP-'0'; GETCHAR(INP); \
    while(DIG(INP)){j=10*j+(INP-'0');GETCHAR(INP);} \
    if (AM) j=-j;\
}
//End of buffer reading

const long double PI = acos((long double) -1.0);
const int oo = 1000111000;

int n, a[222], b[222], za, zb, f[222][222][222];
int na[222], nb[222];
bool cal[222][222][222];

void update(int &a, int b) {
    a = max(a, b);
}

int main() {
    scanf("%d", &n);
    int t = 0;
    FOR(i,1,n) {
        scanf("%d", &a[i]);
        if (!a[i]) ++za;
        else na[++t] = a[i];
    }
    t = 0;
    FOR(i,1,n) {
        scanf("%d", &b[i]);
        if (!b[i]) ++zb;
        else nb[++t] = b[i];
    }

    FOR(i,0,n+1)
        FOR(x,0,za)
        FOR(y,0,zb)
            f[i][x][y] = -oo;

    f[0][0][0] = 0;
    FOR(i,0,n-1)
        FOR(x,0,min(i,za))
        FOR(y,0,min(i,zb)) if (f[i][x][y] > -oo) {
            int nza = i - x;
            int nzb = i - y;
            // 0 & 0
            if (x < za && y < zb)
                update(f[i+1][x+1][y+1], f[i][x][y]);

            // !0 & 0
            if (nza < n-za && y < zb)
                update(f[i+1][x][y+1], f[i][x][y]);

            // 0 & !0
            if (x < za && nzb < n-zb)
                update(f[i+1][x+1][y], f[i][x][y]);

            // !0 & !0
            if (nza < n-za && nzb < n-zb)
                update(f[i+1][x][y], f[i][x][y] + na[nza+1]*nb[nzb+1]);
        }
    cout << f[n][za][zb] << endl;
    return 0;
}

Code mẫu của hieult

#include<cstdio>
#include<cmath>
#include<math.h>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#include<algorithm>
#include<iterator>
#include<iostream>
#include<cctype>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<list>
#define fi first
#define se second
#define PB push_back
#define MP make_pair
#define ep 0.00001
#define oo 111111111
#define base 100000000
#define mod 15111992
#define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
#define rep(i, n) for(int i = 0; i < n; i++)
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FORD(i, a, b) for(int i = a; i >= b; i--)
//#define g 9.81
double const PI=4*atan(1.0);

using namespace std;

typedef pair<int, int> II;
typedef vector<int> VI;
typedef vector<II> VII;
typedef vector<VI> VVI;
typedef vector<VII> VVII;
typedef long long int64;

void OPEN(){
    freopen("A.in","r",stdin);
    freopen("A.out","w",stdout);
}

#define maxn 100005

int f[205][205][205];
int n, a[205], b[205], x;

string reverse(string x){
    string res;
    for(int i = x.length() - 1; i >= 0; i--)
        res.PB(x[i]);
    return res;
}

int main(){
  //  OPEN();
    scanf("%d", &n);
    int asize = 0, bsize = 0;
    rep(i, n){
        scanf("%d", &x);
        if(x != 0){
            a[++asize] = x;
        }
    }
    rep(i, n){
        scanf("%d", &x);
        if(x != 0){
            b[++bsize] = x;
        }
    }

    memset(f, 0x80, sizeof(f));
    //printf("%d\n",f[0][0][0]);

    f[0][0][0] = 0;
    int res = -oo;

    FOR(i, 1, n) for(int j = 0; j <= i && j <= n - asize; j++) for(int k = 0; k <= i && k <= n - bsize; k++){
        if(j == i || k == i){
            f[i][j][k] = 0;
            res = max(res, 0);
            continue;
        }
        if(j > 0 && k > 0)
            f[i][j][k] = f[i - 1][j - 1][k - 1];
        if(j > 0) f[i][j][k] = max(f[i][j][k], f[i - 1][j - 1][k]);
        if(k > 0) f[i][j][k] = max(f[i][j][k], f[i - 1][j][k - 1]);
        f[i][j][k] = max(f[i][j][k], f[i - 1][j][k] + a[i - j] * b[i - k]);
        //printf("%d %d %d ** %d",i,j,k,f[i][j][k]);
        if(i == n) res = max(res, f[i][j][k]); 
    }

    printf("%d",res);
}

Code mẫu của skyvn97

#include<cstdio>
#include<vector>
#define MAX   222
#define REP(i,n) for (int i=0;i<(n);i=i+1)
using namespace std;
const int INF=(int)1e9+7;
int f[MAX][MAX][MAX];
int n;
vector<int> a,b;
void maximize(int &x,const int &y) {
    if (x<y) x=y;
}
void init(void) {
    scanf("%d",&n);
    REP(i,n) {
        int t;
        scanf("%d",&t);
        if (t!=0) a.push_back(t);
    }
    REP(i,n) {
        int t;
        scanf("%d",&t);
        if (t!=0) b.push_back(t);
    }
}
void optimize(void) {
    REP(i,n+1) REP(j,a.size()+1) REP(k,b.size()+1) f[i][j][k]=-INF;
    f[0][0][0]=0;
    REP(i,n+1) REP(j,a.size()+1) REP(k,b.size()+1) if (f[i][j][k]>-INF)
        REP(ca,2) REP(cb,2) if (j+ca<=a.size() && k+cb<=b.size())
            maximize(f[i+1][j+ca][k+cb],f[i][j][k]+ca*cb*a[j]*b[k]);
    printf("%d",f[n][a.size()][b.size()]);
}
int main(void) {
    init();
    optimize();
    return 0;
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.