JZOJ 1322コインゲーム

3173 ワード

ダイナミック？プログラムゲームをする

テーマ:
FJの乳牛はコインゲームが好きなので、FJは新しいコインゲームを発明しました.最初はN(5<=N<=2000)個の硬貨が積み重なっていて、上から数えてi番目の硬貨には整数値Cがあります.i(1<=C_i<=100,000). 2人のプレイヤーが交代で上からコインを取り、プレイヤー1が先に取り、上から1つまたは2つのコインを取ることができ、次のプレイヤーが取ることができるコインの数は最低1つで、最大1人のプレイヤーが取る数の2倍で、コインはすべて試合が終了します.プレイヤー2が極めて賢いことが知られており、最良の戦略を採用しています.今、プレイヤー1が取得したコインの値と最大になるように、プレイヤー1を助けてください.
問題:
プレイヤーが取得したコインの値を最大にするには、プレイヤーが取得したコインの値からプレイヤー2が取得したコインの値を最大に減らすと、ゲーム関数の味がするようになり、後のdpでより便利になります.fi,jは以前の人がi番目のコインを取ったことを示し,現在の人はi+1個から取って,前の人はj個を取って,現在の人が得ることができるコイン数と別の人のコイン数の最大の差を示し,この差はプラスとマイナスであり,逆に別の人への影響に転化する.fi,j=max(sumi+1.k−fk,k−i(1<=k<=2∗j))はO(n 3)である.fi,j,fi,j−1の遷移には大きな共通部分があることが分かったので,fi,j=max(fi,j−1,sumi+1..k−fk,k−i(2∗(j−1)Code:

#include
#define fo(i, x, y) for(int i = x; i <= y; i ++)
#define fd(i, x, y) for(int i = x; i >= y; i --)
#define min(a, b) ((a) < (b) ? (a) : (b))
#define max(a, b) ((a) > (b) ? (a) : (b))
using namespace std;

const int Maxn = 2005;

int n, c[Maxn], s[Maxn], f[Maxn][Maxn];

int main() {
    scanf("%d", &n);
    fo(i, 1, n) scanf("%d", &c[i]);
    if(n == 1) {
        printf("%d
", c[1]); return 0;
    }
    fo(i, 1, n) s[i] = s[i - 1] + c[i];
    fd(i, n - 1, 1) {
        int max = -1e9;
        fo(j, 1, i) {
            fo(k, min(i + 2 * j - 2, n) + 1, min(i + 2 * j, n))
                max = max(max, s[k] - s[i] - f[k][k - i]);
            f[i][j] = max;
        }
    }
    printf("%d", (s[n] +  max(c[1] - f[1][1], c[1] + c[2] - f[2][2])) / 2);
}

4.22注入jsにaddjavascriptinterfaceを追加する必要がある

WebView+H 5ハイブリッド開発まとめ