Editorial for A Coin Game
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
const fi=''; fo=''; maxn=2001; var n,re:longint; f:array[0..maxn,1..maxn] of longint; a,s:array[0..maxn] of longint; procedure rf; var i,x:longint; begin assign(input,fi); reset(input); read(n); for i:=1 to n do read(a[i]); s[0]:=0; for i:=n downto 1 do s[n-i+1]:=s[n-i]+a[i]; close(input); end; function min(x,y:longint):longint; begin if x<y then min:=x else min:=y; end; function max(x,y:longint):longint; begin if x>y then max:=x else max:=y; end; procedure pr; var i,j,k:longint; begin for i:=1 to n do for j:=1 to n do begin f[i,j]:=f[i,j-1]; if j*2-1<=i then f[i,j]:=max(f[i,j],s[i]-f[i-2*j+1,2*j-1]); if j*2<=i then f[i,j]:=max(f[i,j],s[i]-f[i-2*j,2*j]); end; end; procedure wf; begin assign(output,fo); rewrite(output); writeln(f[n,1]); close(output); end; begin rf; pr; wf; end.
Code mẫu của ladpro98
#include <bits/stdc++.h> const int N = 2020; using namespace std; int a[N], F[N][N], maxF[N][N]; int n; int main() { ios :: sync_with_stdio(0); cin.tie(); cin >> n; for(int i = 1; i <= n; i++) cin >> a[i]; reverse(a + 1, a + 1 + n); for(int i = 1; i <= n; i++) a[i] += a[i - 1]; for(int i = 1; i <= n; i++) for(int j = 1; j <= i; j++) { F[i][j] = a[i] - maxF[i - j][min(j + j, i - j)]; maxF[i][j] = max(maxF[i][j - 1], F[i][j]); } cout << max(F[n][1], F[n][2]); return 0; }
Code mẫu của RR
{$MODE OBJFPC} uses math; const MAXN = 4011; var n : longint; f : array[1..MAXN,1..MAXN] of longint; s,c : array[1..MAXN] of longint; procedure inp; var i:longint; begin read(n); for i:=1 to n do read(c[i]); for i:=n downto 1 do s[i]:=s[i+1]+c[i]; end; procedure solve; var i,k:longint; begin for i:=n downto 1 do for k:=1 to n do if k=1 then f[i,k]:=s[i]-f[i+1,2] else f[i,k]:=max(f[i,k-1],s[i]-f[i+k,min(k*2,n)]); writeln(max(f[1,1],f[1,2])); end; begin inp; solve; end.
Code mẫu của hieult
#include <iostream> #include <cstdio> //#include <conio.h> int tong[2010],boc[2010][2010],n,a[2010]; int max(int a,int b) {return a>b?a:b ;} int main() { scanf("%d",&n); for(int i = 1;i<=n;i++) scanf("%d",&a[n+1-i]); for(int i = 1;i<=n;i++) tong[i] = tong[i-1]+a[i]; for(int i = 1;i<=n;i++) for(int j = 1;j<=n;j++) { boc[i][j] = max(boc[i][j],boc[i][j-1]); if(i>=2*j-1) boc[i][j] = max(boc[i][j],tong[i]-boc[i-2*j+1][2*j-1]); if(i>=2*j) boc[i][j] = max(boc[i][j],tong[i]-boc[i-2*j][2*j]); } printf("%d",boc[n][1]); //getch(); }
Code mẫu của ll931110
#include <algorithm> #include <bitset> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <deque> #include <fstream> #include <iostream> #include <iterator> #include <map> #include <queue> #include <set> #include <sstream> #include <string> #include <vector> typedef long long ll; using namespace std; int a[2010],sum[2010],dp[2010][2010]; int n; int main() { // freopen("xoinc.in","r",stdin); // freopen("xoinc.ou","w",stdout); scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", &a[n + 1 - i]); memset(sum,0,sizeof(sum)); for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + a[i]; memset(dp,0,sizeof(dp)); for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) { dp[i][j] = dp[i][j - 1]; if (i >= 2 * j - 1) dp[i][j] = max(dp[i][j],sum[i] - dp[i - (2 * j - 1)][2 * j - 1]); if (i >= 2 * j) dp[i][j] = max(dp[i][j],sum[i] - dp[i - 2 * j][2 * j]); }; printf("%d\n", dp[n][1]); };
Code mẫu của khuc_tuan
#include <iostream> #include <cstdio> using namespace std; int n, a[2020], S; int F[2020][2020], M[2020][2020]; int main() { scanf("%d", &n); for(int i=0;i<n;++i) { scanf("%d", a+i); S += a[i]; } for(int i=n-1;i>=0;--i) { int total = 0; for(int j=1;i+j<=n;++j) { total += a[i+j-1]; int z = 2 * j; if(z + i + j > n) z = n - i - j; F[i][j] = total - M[i+j][z]; } M[i][1] = F[i][1]; for(int j=2;j+i<=n;++j) M[i][j] = max( M[i][j-1], F[i][j]); } int best = max( M[0][1], M[0][2]); cout << (S + best) / 2 << endl; return 0; }
Comments