9.4吉比特笔试情况 + 第三题代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 105;
#define ll long long
#define inf 0x3f3f3f3f3f3f3f3f
ll a[maxn],dp[maxn][maxn][2],sum[maxn],ans = -inf;
//0->A,1->B
int cnt = 0;
ll dfs(int l,int r,int op)
{
    if(l > r)
    {
        return 0;
    }
    ll tt = 0;
    if(op == 0 && dp[l][r][op] != -inf)
        return dp[l][r][op];
    else if(op == 1 && dp[l][r][op] != inf)
        return dp[l][r][op];
    ll mx = -inf,mi = inf;
    for(int i = l; i <= r; i++)
    {
        if(op)
            tt = -sum[i]+sum[l-1];
        else
            tt = sum[i]-sum[l-1];
        ll t = dfs(i+1,r,op^1);
        mx = max(mx,t+tt);
        mi = min(mi,t+tt);
    }
    for(int i = r; i >= l; i--)
    {
        if(op)
            tt = -sum[r]+sum[i-1];
        else
            tt = sum[r]-sum[i-1];
        ll t = dfs(l,i-1,op^1);
        mx = max(mx,t+tt);
        mi = min(mi,t+tt);
    }
    if(op == 0)
        dp[l][r][0] = max(dp[l][r][0],mx);
    else
        dp[l][r][1] = min(dp[l][r][1],mi);
    return dp[l][r][op];
}
int main()
{
    ios::sync_with_stdio(0);
    int n;
    cin>>n;
    for(int i = 1; i <= n; i++)
        cin>>a[i];
    for(int i = 1; i <= n; i++)
        sum[i] = sum[i-1]+a[i];
    for(int i = 1; i <= n; i++)
        for(int j = i; j <= n; j++)
            dp[i][j][0] = -inf,dp[i][j][1] = inf;
    cout<<dfs(1,n,0);
    return 0;
}