马贼分金

目标

    

    让A取得尽可能多的金子。

规则

     

    A可以自由策略；

    B只有简单的贪心策略。

样例数据

 ·    

    2 4 20 25 5 2 7 9 10 9

答案

    A可获得最多的金子数为49。

    A->9; B->10;
    A->9; B->7;
    A->2(右边的2); B->5;
    A->25; B->20;
    A->4; B->2;

分析

      如果我们选用暴力枚举的话，因为B的每一次面对选择只有一种情况，所以复杂度大大降低。利用递归反复调用，模拟出所有情况，当调用到第n层时检查结果。

代码

#include<cstdio>
#include<algorithm>
#define MAXN 105
using namespace std;
int a[MAXN],n;
int ansA,ansB,cou;
void Dfs(int l,int r,int k) {
    if(k == n) {
        cou++;
        printf('A:%d B:%d\n',ansA,ansB);
        return;
    }
    if(k%2 == 0) {
        ansA += a[l];
        Dfs(l+1,r,k+1);
        ansA -= a[l];
        ansA += a[r];
        Dfs(l,r-1,k+1);
        ansA -= a[r];
    }
    else {
        if(a[l] >= a[r]) {
            ansB += a[l];
            Dfs(l+1,r,k+1);
            ansB -= a[l];
        }
        else {
            ansB += a[r];
            Dfs(l,r-1,k+1);
            ansB -= a[r];
        }
    }
    return;
}
int main() {
    freopen('ans.out','w',stdout);
    scanf('%d',&n);
    for(int i = 1; i <= n; i++) {
        scanf('%d',&a[i]);
    }
    Dfs(1,n,0);
    printf('Totil = %d\n',cou);
    return 0;
}

深度分析

     

    我们要找的状态为 max(A),那么我们再来分析一下题意，可以看出金子的总数是不变的。那么想让A取得的越大，B取得的自然就越小，所以不难得出一个关系转化max(A) = min(B);

    这一关系在本题看来并没有什么太大的用处，不过我们稍稍的修改一下游戏规则。A可以随意取，B也可以随意取。A想让自己的金子越多，而B也想让自己的金子越多。（这不就打起来了吗）那么在这样的问题里我们有两个目标，分别是max(A)和max(B),很明显现在是一个二元状态下的问题。我们都学习过二元方程和一元方程，他们时间的复杂关系是不言而喻的。那么如果可以把他们之间的二元关系转换成一元关系，那么就可以大大简化了。

    根据刚刚推出的关系式max(A) = min(B)，同理可得max(B) = min(A)，于是我们的目标就变成了max(A)和min(A)，我们成功地转换成了一个一元状态下问题，接下来B要做的就是阻碍A了。

可得区间动态规划的动态转移方程

A:dp[i][j]=max(dp[i+1][j]+a[i],dp[i][j-1]+a[j]);

B:dp[i][j]=min(dp[i+1][j],dp[i][j-1]);