馬賊分金

長沙7喜 2019-10-19

展開全文

目標

讓A取得盡可能多的金子。

規(guī)則

A可以自由策略；

B只有簡單的貪心策略。

樣例數(shù)據(jù)

2 4 20 25 5 2 7 9 10 9

答案

A可獲得最多的金子數(shù)為49。

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

分析

如果我們選用暴力枚舉的話，因為B的每一次面對選擇只有一種情況，所以復雜度大大降低。利用遞歸反復調(diào)用，模擬出所有情況，當調(diào)用到第n層時檢查結(jié)果。

代碼

#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;
}

深度分析

我們要找的狀態(tài)為 max(A),那么我們再來分析一下題意，可以看出金子的總數(shù)是不變的。那么想讓A取得的越大，B取得的自然就越小，所以不難得出一個關(guān)系轉(zhuǎn)化max(A) = min(B);

這一關(guān)系在本題看來并沒有什么太大的用處，不過我們稍稍的修改一下游戲規(guī)則。A可以隨意取，B也可以隨意取。A想讓自己的金子越多，而B也想讓自己的金子越多。（這不就打起來了嗎）那么在這樣的問題里我們有兩個目標，分別是max(A)和max(B),很明顯現(xiàn)在是一個二元狀態(tài)下的問題。我們都學習過二元方程和一元方程，他們時間的復雜關(guān)系是不言而喻的。那么如果可以把他們之間的二元關(guān)系轉(zhuǎn)換成一元關(guān)系，那么就可以大大簡化了。

根據(jù)剛剛推出的關(guān)系式max(A) = min(B)，同理可得max(B) = min(A)，于是我們的目標就變成了max(A)和min(A)，我們成功地轉(zhuǎn)換成了一個一元狀態(tài)下問題，接下來B要做的就是阻礙A了。

可得區(qū)間動態(tài)規(guī)劃的動態(tài)轉(zhuǎn)移方程

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]);