9.4吉比特笔试情况 + 第三题代码
选择填空都有点耗时，编程第二题题意不清。
调查一下编程题AC情况。
第一题模拟。 第二题题意没懂。
第三题代码存了一下，写的记忆化搜索，其实本质上是区间dp，从小范围到大范围写就好了，一开始瞎写的搜索干脆就将错就错了。
#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;
}
