[TIOJ]1388. 好強的史萊姆

題目連結：http://tioj.infor.org/problems/1388

dp[l][r]代表區間(l,r)的最佳解，而(r-l+1)的奇偶將判斷他們是要用加的還是減的。

#include <iostream>
#define lld long long
#define jizz cin.tie(0);ios_base::sync_with_stdio(0);
#define endl '\n'
using namespace std;
lld dp[105][105];
int main(){jizz
    int n;
    while(cin >> n){
        fill(&dp[0][0],&dp[105][105],0);
        for(int i = 1; i <= n ; i++)cin >> dp[i][i];
        for(int j = 2; j <= n ; j++){
            for(int i = j-1 ; i >= 1 ; i--){
                for(int k = i ; k < j ; k++){
                    dp[i][j] = max(dp[i][j],((j-i+1)&1 ? dp[i][k]*dp[k+1][j] : dp[i][k]+dp[k+1][j]));
                }
            }
        }
        cout << dp[1][n] << endl;
    }
    return 0;
}