题解：SP1710 TWENDS - Two Ends

LookatSea · 2026-07-24 11:16:47 · 题解

区间 dp 好题

令 dp_{l,r} 为区间 l,r 最大分差。

由于初始牌数为偶数，先手先取，因此轮到先手时，区间长度一定是偶数。于是我们只需要求出偶数区间的 dp 值。

然后先手每次取有左右两端点的取值方法，所以分类讨论一下：

1. 取左端点的情况

• 当 a_l+1 \le a_r 时，后手取左边的。状态转移方程为 dp_{l,r}=a_l-a_{l+1}+dp_{l+2,r}。

• 否则后手取右边的，状态转移方程为 dp_{l,r}=a_l-a_r+dp_{{l+1},{r-1}}。

2. 取右端点的情况

• 当 a_l \le a_{r-1} 时，后手取左边的。状态转移方程为 dp_{l,r}=a_r-a_l+dp_{{l+1},{r-1}}。

• 否则后手取右边的，状态转移方程为 dp_{l,r}=a_r-a_{r-1}+dp_{l,{r-2}}。

然后两种情况取最大值就好了。

#include<bits/stdc++.h>
using namespace std;
int n;
int a[1005],dp[1005][1005];
int main(){
    int cnt=0;
    while(cin>>n&&n!=0){
        cnt++;
        memset(a,0,sizeof(a));
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++) cin>>a[i];
        for(int i=2;i<=n;i+=2){
            for(int l=1;l+i-1<=n;l++){
                int r=l+i-1,ans1=0,ans2=0;
                if(a[l+1]>=a[r]) ans1=a[l]-a[l+1]+dp[l+2][r];
                else ans1=a[l]-a[r]+dp[l+1][r-1];
                if(a[l]>=a[r-1]) ans2=a[r]-a[l]+dp[l+1][r-1];
                else ans2=a[r]-a[r-1]+dp[l][r-2];
                dp[l][r]=max(ans1,ans2);
            }
        }
        printf("In game %d, the greedy strategy might lose by as many as %d points.\n",cnt,dp[1][n]); 
    }
    return 0;
}