[題解]TIOJ 1029 A遊戲

1029 A遊戲

有一串由N個正整數所組成的數列，兩個玩者輪流拿走一個最左邊或最右邊的數，直到最後所有的數都取完之後，兩個玩者分別把自己所取到數加總，分數較高的人獲勝。
範例輸入
6
4 7 2 9 5 2
輸出 18 11

定義

這一題用到的是區間DP
定義dp[i][j]為區間$[i,j]$中先手可以拿到的最大值，因為先後手拿的總和不變，所以後手在區間$[i,j]$ 可以拿到的最大值為 $sum[i,j]-dp[i][j]$。
同時，$dp[i][i] = arr[i]$ (先手取)

轉移方式

由題目可知，先後手都是以最佳策略來玩這個遊戲，而區間$[l,r]$中先手在區間$[l+1,r]$ 中就變成後手（對手先拿），因此可以推得轉移式：

$dp[i][j] = max(sum[i+1,j]-dp[i+1][j]+arr[i], sum[i,j-1]-dp[i][j-1]+arr[j])$

（第一項取最左邊，第二項代表取最右邊）

以此圖為例，以i為橫軸代表出發點，j為縱軸代表終點，由上而下、由右而左依序把左下角的表格填滿。所求即為(i,j) = (1,6)。

邊界條件

$dp[i][i] = arr[i]$

程式碼

上方的sum，可以透過表格儲存前綴和，快速求得

#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0);cin.tie(0);
using namespace std;
int n;

int main(){
    ios
    cin>>n;
    int dp[n+1][n+1],pref[n+1],arr[n+1];
    memset(dp,0,sizeof(dp));
    pref[0] = 0;
    for(int i=1;i<=n;i++){
        cin>>arr[i];
        dp[i][i] = arr[i];
        pref[i] = pref[i-1]+arr[i];
    }
    for(int i=n-1;i>0;i--){
        for(int j=i+1;j<=n;j++){
            dp[i][j] = max(pref[j]-pref[i]-dp[i+1][j]+arr[i],//右格
                           pref[j-1]-pref[i-1]-dp[i][j-1]+arr[j]);//上格
        }
    }
    cout<<dp[1][n]<<" "<<pref[n]-dp[1][n]<<endl;
    
//    for(int j=1;j<n+1;j++){
//        for(int i=1;i<=n;i++)cout<<dp[i][j]<<" ";
//        cout<<endl;//印出dp
//    }
}

Leetcode 877這裡有一系列的stone game 變化題

class Solution {
public:
    bool stoneGame(vector<int>& piles) {
        int n = piles.size();
        piles.insert(piles.begin(),0);
        int dp[n+1][n+1],pref[n+1];
        memset(dp,0,sizeof(dp));
        memset(pref,0,sizeof(pref));
        for(int i=1;i<=n;i++){
            dp[i][i] = piles[i];
            pref[i] = pref[i-1]+piles[i];
        }
        
        for(int i=n-1;i>0;i--){
            for(int j=i+1;j<=n;j++){
                dp[i][j] = max(pref[j]-pref[i]-dp[i+1][j]+piles[i],
                              pref[j-1]-pref[i-1]-dp[i][j-1]+piles[j]);
            }
        }
        cout<<dp[1][n]<<endl;
        if(dp[1][n]>pref[n]/2)return true;
        else return false;
    }
};

這一題有一個數學解，可以保證答案一定是true。

We can extend this idea to N piles. Say the first, third, fifth, seventh, etc. piles are white, and the second, fourth, sixth, eighth, etc. piles are black. Alex can always take either all white piles or all black piles, and one of the colors must have a sum number of stones larger than the other color.

簡單來說，alex可以控制對方拿到的一定是白色堆或是黑色堆，因此只要在一開始選擇數量較大的顏色就保證可以贏得遊戲

複雜度

$O(N^2)$

這一題除了轉移式比較難想之外，要怎麼樣轉移也是一個問題。轉移方式可以透過小範圍測資試著找轉移的規律，如何轉移則可以透過畫表格的方式理解。