題意

一個數串
A和B每人從這個數串的第一個或者最后一個元素選擇一個數加到自己的得分里，A先選，求先手最大得分
樣例：
4
-1 0 100 2
輸出
99

分析

對于任意一個區間段 我們考慮的問題是相似的
不論任何區間段都是考慮取前面的還是取后面的
我們要從兩種策略里選出一個更優的
對這個序列 我們每次都是從左或是從右選擇一個元素拿出來
所以問題就相當于在從i到j的區間段里
如何表示兩種策略那就是拿前面的和拿后面的計算結果
我們就把這個結果存到一個二維數組中
假設我們問題n==1
那么直接就能返回結果 得到最大先手
假設問題規模為2
那么就相當于選擇左邊的元素 那么對方的得分就是f(i+1,e)
先手得分就是sum[e]-sum[i-1]-f(i+1,e)
右邊同理 我們選取兩個中的那個最大的結果
當區間長度覆蓋了全部區間段時就是我們要的結果

#include<bits/stdc++.h> using namespace std; int a[1010],f[1010][1010],sum[1010]; int main() {int n;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);f[i][i]=a[i];sum[i]=sum[i-1]+a[i];}/*f[i][j]表示從i開始到j先手所能獲取的最大值 */for(int i=2;i<=n;i++){for(int j=1;j<=n-i+1;j++){int e = j+i-1;f[j][e] = max(sum[e]-sum[j-1]-f[j+1][e],sum[e]-sum[j-1]-f[j][e-1]);}}printf("%d\n",f[1][n]);return 0; }

總結

以上是生活随笔為你收集整理的hihocoder A Game 区间dp的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。