【題解】TIOJ 1029 . A遊戲

【題目敘述】https://tioj.ck.tp.edu.tw/problems/1029
【解題想法】DP

  • a[i][j]:剩下 [i, j] 個數字時,玩家能拿到的最高分數。a[i][i]為輸入的測資。
  • s:所有數字的總和。
  • DP 狀態轉移方程:Line-12。因為更新DP時,會用到下標 i – 2,所有的陣列下標先平移 2。
#include <iostream>
using namespace std;
 
int n, s, a[1005][1005];
 
int main() {
    cin >> n;
    for (int i = 2; i < n+2; i++){
        cin >> a[i][i];
        s += a[i][i];
        for (int j = i-1; j >= 2; j--){
            a[j][i] = max(a[j][j] + min(a[j+1][i-1], a[j+2][i]),
                          a[i][i] + min(a[j][i-2], a[j+1][i-1]));
        }
    }
    cout << a[2][n+1] << " " << s - a[2][n+1] << "\n";
}
分享本文 Share with friends