3.3.5 A Game 游戏

3.3.5 A Game 游戏

时间: 1ms        内存:64M

描述:

有如下一个双人游戏:N(2 <= N <= 100)个正整数的序列放在一个游戏平台上,两人轮流从序列的两端取数,取数后该数字被去掉并累加到本玩家的得分中,当数取尽时,游戏结束。以最终得分多者为胜。 编一个执行最优策略的程序,最优策略就是使自己能得到在当前情况下最大的可能的总分的策略。你的程序要始终为第二位玩家执行最优策略。

输入:

第一行: 正整数N, 表示序列中正整数的个数。
第二行至末尾: 用空格分隔的N个正整数(大小为1-200)。

输出:

只有一行,用空格分隔的两个整数: 依次为玩家一和玩家二最终的得分。

示例输入:

6 
4 7 2 9
5 2

示例输出:

18 11

提示:

参考答案(内存最优[1316]):

/*
ID:zhaofuk1
PROG: game1
LANG: C++
*/
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 110;
int Digit[MAXN];
int ans[MAXN][MAXN];
int dp(int x, int y, int sum)
{
    int &an = ans[x][y];
    if(an != -1) return an;
    if(x == y) return an = Digit[x];
    return an = max(Digit[x] + sum - Digit[x] - dp(x + 1, y, sum - Digit[x]), Digit[y] + sum - Digit[y] - dp(x, y - 1, sum - Digit[y]));
}

int main()
{
    //freopen("game1.in", "r", stdin);
    //freopen("game1.out", "w", stdout);
    int n;
    int x, y, sum = 0;
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        scanf("%d", &Digit[i]);
        sum += Digit[i];
    }
    memset(ans, -1, sizeof(ans));
    x = dp(0, n - 1, sum);
    printf("%d %d\n", x, sum - x);
    return 0;
}

参考答案(时间最优[12]):

/*
ID:zhaofuk1
PROG: game1
LANG: C++
*/
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 110;
int Digit[MAXN];
int ans[MAXN][MAXN];
int dp(int x, int y, int sum)
{
    int &an = ans[x][y];
    if(an != -1) return an;
    if(x == y) return an = Digit[x];
    return an = max(Digit[x] + sum - Digit[x] - dp(x + 1, y, sum - Digit[x]), Digit[y] + sum - Digit[y] - dp(x, y - 1, sum - Digit[y]));
}

int main()
{
    //freopen("game1.in", "r", stdin);
    //freopen("game1.out", "w", stdout);
    int n;
    int x, y, sum = 0;
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        scanf("%d", &Digit[i]);
        sum += Digit[i];
    }
    memset(ans, -1, sizeof(ans));
    x = dp(0, n - 1, sum);
    printf("%d %d\n", x, sum - x);
    return 0;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注