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.
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