一開始傻呼呼的以為是一題標準模擬題
想用deque一直比大小
後來一直WA生氣跑去網路查
才找到區間dp的提示ww(由後往前推的概念,要再多看看,想一下)
#include <bits/stdc++.h>
using namespace std;
int n, s, a[1005][1005];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
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";
}
果然…
建中校內賽prob 6不是什麼簡單題
不要自作多情XD
另外區間dp也要多注意