Editorial for IOI07 Miners
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
uses math; const fi=''; oo=1000000000; var f:array[0..1,0..3,0..3,0..3,0..3] of longint; g:array[0..3,0..3,0..3] of longint; h:array[1..10,0..1] of longint; e:array[0..3] of longint; n,i,z,re,a,b,c,d,x,p,q:longint; ch:char; procedure rset(z:longint); var a,b,c,d:longint; begin for a:=0 to 3 do for b:=0 to 3 do for c:=0 to 3 do for d:=0 to 3 do f[z,a,b,c,d]:=-oo; c:=0; for a:=1 to 3 do for b:=1 to 3 do begin inc(c); h[c,0]:=a; h[c,1]:=b; end; h[10,0]:=0; h[10,1]:=0; end; function calc(a,b,c:longint):longint; var i,r:longint; begin r:=0; for i:=1 to 3 do e[i]:=0; inc(e[a]); inc(e[b]); inc(e[c]); for i:=1 to 3 do if e[i]>0 then inc(r); calc:=r; end; begin assign(input,fi); reset(input); readln(n); rset(0); rset(1); f[0,0,0,0,0]:=0; for a:=0 to 3 do for b:=0 to 3 do for c:=0 to 3 do g[a,b,c]:=calc(a,b,c); for i:=1 to n do begin z:=i and 1; read(ch); case ch of 'M':x:=1; 'F':x:=2; else x:=3; end; for p:=1 to 10 do for q:=1 to 10 do if (p<>10) or (q<>10) or (i=1) then begin a:=h[p,0]; b:=h[p,1]; c:=h[q,0]; d:=h[q,1]; if p+q=20 then begin f[z,0,0,x,x]:=1; f[z,x,x,0,0]:=1; end else begin if p=10 then begin f[z,x,x,c,d]:=max(f[z,x,x,c,d],f[1-z,0,0,c,d]+1); f[z,0,0,d,x]:=max(f[z,0,0,d,x],f[1-z,0,0,c,d]+g[c,d,x]); end else begin if q=10 then begin f[z,a,b,x,x]:=max(f[z,a,b,x,x],f[1-z,a,b,0,0]+1); f[z,b,x,0,0]:=max(f[z,b,x,0,0],f[1-z,a,b,0,0]+g[a,b,x]); end else begin f[z,b,x,c,d]:=max(f[z,b,x,c,d],f[1-z,a,b,c,d]+g[a,b,x]); f[z,a,b,d,x]:=max(f[z,a,b,d,x],f[1-z,a,b,c,d]+g[c,d,x]); end; end; end; end; end; re:=n; for a:=0 to 3 do for b:=0 to 3 do for c:=0 to 3 do for d:=0 to 3 do re:=max(re,f[z,a,b,c,d]); writeln(re); close(input); end.
Code mẫu của happyboy99x
#include<iostream> #include<cstring> using namespace std; const int N = 100000; int f[N + 1][4][4][4][4]; int numDistinct(int x, int y, int z) { if(x == 3) return y == 3 || y == z ? 1 : 2; if(y == 3) return 1; if(x != y && x != z && y != z) return 3; if(x == y && x == z) return 1; return 2; } void checkMax(int &x, int y) { if(x < y) x = y; } int main() { #ifndef ONLINE_JUDGE freopen("NKMINERS.inp", "r", stdin); #endif ios::sync_with_stdio(false); int n; string s; cin >> n >> s; memset(f, 0xc1, sizeof f); int res = 0; f[0][3][3][3][3] = 0; for(int i = 0; i <= n; ++i) { int type = i == n ? -1 : s[i] == 'M' ? 0 : s[i] == 'F' ? 1 : 2; for(int x1 = 0; x1 < 4; ++x1) { for(int y1 = 0; y1 < 4; ++y1) { for(int x2 = 0; x2 < 4; ++x2) { for(int y2 = 0; y2 < 4; ++y2) { if(f[i][x1][y1][x2][y2] >= 0) { if(i < n) { checkMax(f[i + 1][y1][type][x2][y2], f[i][x1][y1][x2][y2] + numDistinct(x1, y1, type)); checkMax(f[i + 1][x1][y1][y2][type], f[i][x1][y1][x2][y2] + numDistinct(x2, y2, type)); } else { checkMax(res, f[i][x1][y1][x2][y2]); } } } } } } } cout << res << '\n'; return 0; }
Code mẫu của ladpro98
#include <cstdio> const int N = 100005; using namespace std; int F[2][4][4][4][4]; int val[4][4][4]; int a[N]; int n, res; void maximize(int& x, int y) { if (x < y) { x = y; if (res < x) res = x; } } int main() { scanf("%d\n", &n); int i, j, k, x1, y1, x2, y2; char c; for(i=1; i<=n; i++) { scanf("%c", &c); if (c == 'M') a[i] = 1; if (c == 'F') a[i] = 2; if (c == 'B') a[i] = 3; } for(i=0; i<=3; i++) for(j=0; j<=3; j++) for(k=0; k<=3; k++) { if (i == 1 || j == 1 || k == 1) val[i][j][k]++; if (i == 2 || j == 2 || k == 2) val[i][j][k]++; if (i == 3 || j == 3 || k == 3) val[i][j][k]++; } int now = 0, next = 1, p, prev; F[now][0][a[1]][0][0] = F[now][0][0][0][a[1]] = 1; for(i=1; i<n; i++) { for(x1=0; x1<=3; x1++) for(y1=(x1 != 0 ? 1 : 0); y1<=3; y1++) for(x2=0; x2<=3; x2++) for(y2=(x2 != 0 ? 1 : 0); y2<=3; y2++) { p = a[i + 1]; prev = F[now][x1][y1][x2][y2]; if (prev == 0) continue; maximize(F[next][y1][p][x2][y2], prev + val[x1][y1][p]); maximize(F[next][x1][y1][y2][p], prev + val[x2][y2][p]); } next ^= 1; now ^= 1; } printf("%d", res); return 0; }
Code mẫu của RR
#include <iostream> #include <algorithm> #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 MAXN 100111 using namespace std; int n,a[MAXN],f[2][4][4][4][4],cnt[4][4][4]; char s[MAXN]; void inp() { scanf("%d\n",&n); gets(s); FOR(i,1,n) if (s[i-1]=='M') a[i]=0; else if (s[i-1]=='F') a[i]=1; else a[i]=2; } void solve() { FOR(x,0,3) FOR(y,0,3) FOR(z,0,3) FOR(t,0,2) if (x==t || y==t || z==t) cnt[x][y][z]++; memset(f,-1,sizeof f); f[0][3][3][3][3]=0; int now=0; FOR(i,0,n-1) { int u=a[i+1]; now=1-now; FOR(a1,0,3) FOR(a2,0,3) FOR(b1,0,3) FOR(b2,0,3) if (f[1-now][a1][a2][b1][b2]>=0) { f[now][a2][u][b1][b2] >?= f[1-now][a1][a2][b1][b2]+cnt[a1][a2][u]; f[now][a1][a2][b2][u] >?= f[1-now][a1][a2][b1][b2]+cnt[b1][b2][u]; } } int res=0; FOR(a1,0,3) FOR(a2,0,3) FOR(b1,0,3) FOR(b2,0,3) res >?= f[now][a1][a2][b1][b2]; printf("%d\n",res); } int main() { inp(); solve(); return 0; }
Code mẫu của hieult
#include<cstdio> #include<cmath> #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> //#include<conio.h> #define ep 0.000000001 #define maxn 10011 #define oo 1111111111 #define base 100000000 #define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++) double const PI=4*atan(1); using namespace std; typedef pair<int, int> II; typedef vector<int> VI; typedef vector<II> VII; typedef vector<VI> VVI; typedef vector<VII> VVII; int f[100111][13][13],n,A; char s[100111]; //VVI::iterator it; int khac (int a1,int a2,int a3){ if(a1==0) return (a2!=a3)+1; if(a1==a2 && a2==a3) return 1; if(a1==a2 && a1!=a3) return 2; if(a1==a3 && a1!=a2) return 2; if(a2==a3 && a1!=a2) return 2; return 3; } int main(){ // freopen("NKMINERS.in","r",stdin); scanf("%d",&n); scanf("%s",s); memset(f,-1,sizeof(f)); f[0][0][0] = 0; for(int ii = 1 ;ii<=n;ii++){ if(s[ii-1]=='M') A = 1; if(s[ii-1]=='B') A = 2; if(s[ii-1]=='F') A = 3; for(int i = 0;i<13;i++){ for(int j = 0;j<=3;j++){ if(j==0){ if(f[ii-1][0][i]!=-1) f[ii][A][i] = f[ii-1][0][i]+1; if(f[ii-1][i][0]!=-1) f[ii][i][A] = f[ii-1][i][0]+1; } else{ for(int k = 0;k<=3;k++){ if(f[ii-1][k*3+j][i]!=-1) f[ii][j*3+A][i] >?= f[ii-1][k*3+j][i]+khac(k,j,A); if(f[ii-1][i][k*3+j]!=-1) f[ii][i][j*3+A] >?= f[ii-1][i][k*3+j]+khac(k,j,A); } } } } } int KQ = 0; for(int i = 0;i<13;i++) for(int j = 0;j<13;j++) KQ >?= f[n][i][j]; printf("%d",KQ); // getch(); }
Code mẫu của ll931110
{$MODE DELPHI,R+,Q+,H+} program NKMINERS; const input = ''; output = ''; maxv = 100000 * 100; maxk = 9; link: array[0..9,1..3] of integer = ((1,2,3),(1,4,5),(6,2,7),(8,9,3), (6,2,7),(8,9,3),(1,4,5),(8,9,3), (1,4,5),(6,2,7)); cost: array[0..9,1..3] of integer = ((1,1,1),(1,2,2),(2,1,2),(2,2,1), (2,2,3),(2,3,2),(2,2,3),(3,2,2), (2,3,2),(3,2,2)); //state: 0[0],1[1],2[2],3[3],12[4],13[5],21[6],23[7],31[8],32[9] var cur,next: array[0..maxk,0..maxk] of integer; n,res: integer; s: string; procedure init; var f: text; begin assign(f, input); reset(f); readln(f, n); readln(f, s); close(f); end; procedure solve; var i,j,t,ek,ds,dc: integer; ch: char; begin for i := 0 to maxk do for j := 0 to maxk do cur[i,j] := -maxv; cur[0,0] := 0; next := cur; for t := 1 to n do begin ch := s[t]; case ch of 'M': ek := 1; 'F': ek := 2; 'B': ek := 3; end; for i := 0 to maxk do for j := 0 to maxk do begin ds := link[i,ek]; dc := cost[i,ek]; if next[ds,j] < cur[i,j] + dc then next[ds,j] := cur[i,j] + dc; ds := link[j,ek]; dc := cost[j,ek]; if next[i,ds] < cur[i,j] + dc then next[i,ds] := cur[i,j] + dc; end; cur := next; end; res := 0; for i := 0 to maxk do for j := 0 to maxk do if res < cur[i,j] then res := cur[i,j]; end; procedure printresult; var f: text; begin assign(f, output); rewrite(f); writeln(f, res); close(f); end; begin init; solve; printresult; end.
Code mẫu của skyvn97
#include<cstdio> #include<cstring> #define MAX 100100 #define FOR(i,a,b) for (int i=(a);i<=(b);i=i+1) #define REP(i,n) for (int i=0;i<(n);i=i+1) #define maximize(x,y) if (x<(y)) x=(y) #define ok int n; char s[MAX]; int f[MAX][4][4][4][4]; inline int count(int x,int y,int z) { bool ex[7]; memset(ex,false,sizeof ex); ex[x]=true; ex[y]=true; ex[z]=true; int ret=0; FOR(i,1,3) if (ex[i]) ret++; return (ret); } void init(void) { scanf("%d",&n); scanf("%s",s+1); FOR(i,1,n) { if (s[i]=='M') s[i]=1; if (s[i]=='F') s[i]=2; if (s[i]=='B') s[i]=3; } } void optimize(void) { f[1][0][s[1]][0][0]=1; f[1][0][0][0][s[1]]=1; FOR(i,1,n-1) REP(p11,4) REP(p12,4) REP(p21,4) REP(p22,4) if (f[i][p11][p12][p21][p22]>0) { maximize(f[i+1][p12][s[i+1]][p21][p22],f[i][p11][p12][p21][p22]+count(p11,p12,s[i+1])); maximize(f[i+1][p11][p12][p22][s[i+1]],f[i][p11][p12][p21][p22]+count(p21,p22,s[i+1])); } int res=0; FOR(p11,1,3) REP(p11,4) REP(p12,4) REP(p21,4) REP(p22,4) maximize(res,f[n][p11][p12][p21][p22]); printf("%d",res); } int main(void) { init(); optimize(); return 0; }
Code mẫu của khuc_tuan
#include <iostream> #include <cstdio> using namespace std; int n; char a[100010]; int f[4][4][4][4], g[4][4][4][4]; int main() { scanf("%d", &n); gets(a); gets(a); memset( f, -1, sizeof(f)); f[3][3][3][3] = 0; for(int i=0;i<n;++i) { memset( g, -1, sizeof(g)); int next = 0; if(a[i]=='M') next = 1; if(a[i]=='F') next = 2; for(int i00=0;i00<4;++i00) for(int i01=0;i01<4;++i01) { for(int i10=0;i10<4;++i10) for(int i11=0;i11<4;++i11) if(f[i00][i01][i10][i11]!=-1) { // cho mo 1 int tmp = 1 + f[i00][i01][i10][i11]; if(i01!=3 && i01!=next) ++tmp; if(i00!=3 && i00!=i01 && i00!=next) ++tmp; int &gg = g[i01][next][i10][i11]; if(gg<tmp) gg = tmp; // cho mo 2 tmp = 1 + f[i00][i01][i10][i11]; if(i11!=3 && i11!=next) ++tmp; if(i10!=3 && i10!=i11 && i10!=next) ++tmp; int &g2 = g[i00][i01][i11][next]; if(g2<tmp) g2 = tmp; } } memmove( f, g, sizeof(f)); } int result = 0; for(int i00=0;i00<4;++i00) for(int i01=0;i01<4;++i01) for(int i10=0;i10<4;++i10) for(int i11=0;i11<4;++i11) if(f[i00][i01][i10][i11]!=-1) result >?= f[i00][i01][i10][i11]; cout << result << endl; //system("pause"); return 0; }
Comments