题意：一个数字序列，每次取最左端或最右端，问在保证先手取得的数字和大于后手取得的数字和的情况下，后手取得的数字和最大是多少
我们进行逆向推演，假设x为最后取得数,那么上一次取得数可能是x+1或x-1,记dp[i][j]表示取值位置范围i-j时先手大于后手获得的价值，且满足后手获得的价值和也最大,dp[i][j]=sum(i,j)-dp[i][j-1]或dp[i+1][j],为获得最大值,则dp[i][j]=sum(i,j)-min(dp[i][j-1],dp[i+1][j]),保证了dp[i][j]都是最大值，先手获得了最大价值,类推可知dp[i+1][j],dp[i][j-1]也是最大值，后手也获得了最大价值。
AC代码
//接着另一题的代码写的，不过问题不大 #include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<string> #include<vector> #include<map> #include<queue> #include<cmath> using namespace std; typedef long long ll; const int N = 2e5 + 100; int arr[N],sum[N], dp[300][300]; vector<int> end_0, end_1,ans; int main() { ios::sync_with_stdio(false); int n; cin >> n; for (int i = 1; i <= n; i++) { cin >> arr[i]; sum[i] = sum[i - 1] + arr[i]; dp[i][i] = arr[i]; } for (int len = 2; len <= n; len++) { for (int l = 1; l + len - 1 <= n; l++) { int r = l + len - 1; dp[l][r] = sum[r] - sum[l - 1] - min(dp[l+1][r],dp[l][r-1]); } } cout << dp[1][n] << " " << sum[n] - dp[1][n] ;//吐槽一下：洛谷评测加个换行竟然WA，疑惑 }