zzuoj-10451: 数字卡片游戏

传送门

动态规划问题

f[i][j]表示剩下区间[i,j]后，取完该区间所有卡片的最优解差值。规定值为正数表示，A胜；

若下一张卡片为A取，则dp[i][j] = max(dp[i+1][j]+num[i], dp[i][j-1]+num[j]);;

若下一张卡片为B取，则dp[i][j] = min(dp[i+1][j]-num[i], dp[i][j-1]-num[j]);；

#include <bits/stdc++.h>
#define N 2003
#define ll long long
using namespace std;
int num[N],n;
int dp[N][N];//dp[i][j]表示取i到j的最优解 
int main(){
#ifndef ONLINE_JUDGE
    freopen("1.txt", "r", stdin);
#endif  
    int i, j, k, t;
    while(~scanf("%d", &n)){
        for (i = ; i <= n; i++){
            scanf("%d", &num[i]);
        }
        memset(dp, , sizeof(dp));
        if (n&){   //判读最后一张是A取还是B取, 如果是A取, dp[i][i] 就初始化为正, 否则初始化为负 
            t = ;
        }else{
            t = -;
        }
        for (i = ; i <= n; i++){
            dp[i][i] = t*num[i];//初始化dp[i][i] 
        }
        for(i = n; i >= ; i--){    //i是递减的 
            for(j = i; j <= n; j++){    //j是递增的 
                if ((n-j+i-)&){
                    dp[i][j] = min(dp[i+][j]-num[i], dp[i][j-]-num[j]);//如果该B取, B会选择使当前差值变小的方案 
                }else{
                    dp[i][j] = max(dp[i+][j]+num[i], dp[i][j-]+num[j]);//如果是A取, A会选择使当前差值变大的方案 
                }
            }
        }
        if (dp[][n] > )//dp[1][n] 就是最后的差值 
            printf("A %d\n", dp[][n]);
        else if (dp[][n] < )
            printf("B %d\n", -dp[][n]);
        else
            puts("A=B");
    }


    return ;
}