【題目敘述】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";
}