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.

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

Please read the guidelines before commenting.


There are no comments at the moment.