f[i][j]表示在区间 [i,j]时,先手和后手的最大差值得分。
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110;
int n;
int w[N], f[N][N];
int main()
{
cin >> n;
int sum = 0;
for (int i = 0; i < n; i ++ ) cin >> w[i], sum += w[i];
for(int len=1;len<=n;len++)
for(int i=0;i<n;i++){
int j=i+len-1;
f[i][j]=max(w[i]-f[i+1][j],w[j]-f[i][j-1]);
}
cout<<(sum+f[0][n-1])/2<<" "<<(sum-f[0][n-1])/2<<endl;
}
f[i][j]表示在区间 [i,j]时,所能获得的最大得分。
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110;
int s[N];
int n;
int w[N], f[N][N];
int main()
{
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> w[i];
s[i] = s[i - 1] + w[i];
}
for(int len=1;len<=n;len++)
for (int i = 1; i <= n; i ++ ){
int j=i+len-1;
f[i][j]=max(w[i]+s[j]-s[i]-f[i+1][j],w[j]+s[j-1]-s[i-1]-f[i][j-1]);
//前缀和不包含i,因为i待选 前缀和不包含j,因为j待选
}
cout << f[1][n]<<" "<<s[n]-f[1][n]<<endl;
}