[INFOR] 15 遊戲問題

題目連結：https://oj.infor.org/problems/15
　　DP，轉移式為dp[i][j] = max(a[i]+...+a[k] - dp[k+1][j], a[j]+...+a[k] - dp[i][k-1])之類的，dp[i][j]代表i~j的解，然後因為N到了1000，所以要欲處理前綴和以O(1)求出區間和。

#include<bits/stdc++.h>
using namespace std;
int n;
int noodle[1009];
int dp[1009][1009];
int input()
{
    int x = 0;
    char cha;
    bool flag = true;
    while(cha = getchar())
    {
        if(cha == '-') flag = false;
        if(cha <= '9' && cha >= '0')
            break;
    }
    x = cha - '0';
    while(cha = getchar())
    {
        if(cha > '9' || cha < '0') break;
        x = (x<<3)+(x<<1)+(cha-'0');
    }
    return (flag)?x:-x;
}
void output(int x)
{
    int res = 0;
    char cha[100];
    if(x < 0) putchar('-');
    x = abs(x);
    if(x == 0) putchar('0');
    while(x != 0)
    {
        cha[res++] = '0'+(x%10);
        x /= 10;
    }
    for(int i = res-1; i >= 0; i--)
        putchar(cha[i]);
    putchar('\n');
}
int main()
{
    n = input();
    for(int i = 1; i <= n; i++)
    {
        dp[i][i] = input();
        noodle[i] = dp[i][i] + noodle[i-1];
    }
    for(int i = 1; i <= n-1; i++)
        for(int j = 1; j <= n-i; j++)
        {
            dp[j][j+i] = -1e9; 
            for(int k = 0; k <= i; k++)
                dp[j][j+i] = max(dp[j][j+i],max(noodle[j+i]-noodle[j+k-1]-dp[j][j+k-1],noodle[j+k]-noodle[j-1]-dp[j+k+1][j+i]));
        }
    output(dp[1][n]);
}