ivana.cpp

Bài toán

Có một vòng tròn chứa n số. Có hai người chơi, lượt đầu tiên, người chơi A đánh dấu một số bất kì. Ở lượt chơi tiếp theo, hai người chơi thay phiên nhau, đánh dấu vào một ô cạnh một ô đã đánh dấu (dĩ nhiên là đánh dấu vào ô chưa được đánh dấu. Mỗi lần đi, người chơi nào mà đánh dấu được vào một số lẻ thì được một điểm. Sau n nước đi thì trò chơi kết thúc, tất nhiên là n số đều đã được đnahs dấu. Dựa vào số điểm chung cuộc, ta có thể biết người chơi A thắng, hòa, hay thua người chơi B. Hỏi có bao nhiêu cách cho người chơi A thăngs cuộc chơi này, tức là có bao nhiêu cách chọn đầu tiên để A thực sự thắng.

Độ phức tạp

O(n^2)

Code này của Nguyễn Tiến Trung Kiên

#include <stdio.h>

#include <algorithm>

using namespace std;

int n;

int a[12309];

int F[345][345];

int FF[345][345];

int f(int ll, int rr){

    if (rr-ll+1==n) return 0;

    if (FF[ll][rr]++) return F[ll][rr];

    int r1 = - f(ll-1, rr) + (a[ll-1]&1);

    int r2 = - f(ll, rr+1) + (a[rr+1]&1);

    return F[ll][rr] = max(r1, r2);

}

main(){

    int i, answer=0;

    scanf("%d", &n);

    for (i=1; i<=n; i++) scanf("%d", &a[i]);

    for (i=1; i<=n; i++) a[i+n+n]=a[i+n]=a[i];

    for (i=1; i<=n; i++) if (-f(i+n, i+n) + (a[i]&1) > 0) answer ++;

    printf("%d\n", answer);

}

Mô tả

int f(int ll, int rr)

người chơi đang đứng ở trạng thái (ll,rr) tức là các ô nằm trong khoảng [ll,rr] đã bị đánh dấu, hỏi xem người chơi thu được bao nhiêu điểm. Ở đây ta coi như nếu đối phương ăn được một điểm thì mình mất một điểm.

Nhận xét

Đây là một bài game cơ bản.