蓝桥杯复训之区间dp

题目链接：https://www.acwing.com/problem/content/1390/

思路：对区间进行动态规划，f[i][j]代表从区间i到j的先手所能拿到的最大值
 

#include<bits/stdc++.h>
using namespace std;
const int N=105;
 
int fg[N][N];
 
int main(){
    int n;cin>>n;
    vector<int>a(n+1);
    int sum[N]={ };
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum[i]=sum[i-1]+a[i];
        fg[i][i]=a[i];
    }
    
    
    for(int len=2;len<=n;len++){
        for(int i=1;i<=n-len+1;i++){
            int j=i+len-1;
            //先手所能拿到的最大值是当前这一段总值减去后手最大值
            fg[i][j]=max(sum[j]-sum[i-1]-fg[i+1][j],sum[j]-sum[i-1]-fg[i][j-1]);
        }
    }
    cout<<fg[1][n]<<' '<<sum[n]-fg[1][n]<<'\n';
}