AcWing---游戏---区间dp

发布于:2024-04-11 ⋅ 阅读:(169) ⋅ 点赞:(0)

1388. 游戏 - AcWing题库 

思路:

两个人比赛,是一道博弈论问题,主要思想就是A-B取到最大值。A是我方得到的分数,B是对方得到的分数。我们设g[i][j]是从第i个数到第j个数,先手-后手取得的最大值,分类讨论,先手选择了第i个数,那么g[i][j]=w[i]-g[i+1][j];先手选择了第j个数,那么g[i][j]=w[j]-g[i][j-1]。两者取最大值就好。

区间dp第一维遍历区间长度,第二维遍历左索引。

C++代码:
 

#include<bits/stdc++.h>
using namespace std;

int n;
int w[110];
int dp[110][110];//dp[i][j]---从i开始到j,先手-后手分数的最大值
//dp[i][j]=max(w[i]-dp[i+1][j],w[j]-dp[i][j-1])

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+len-1<n;i++){
            int j=i+len-1;
            if(i+1<n && j-1>=0){
                dp[i][j]=max(w[i]-dp[i+1][j],w[j]-dp[i][j-1]);
            }
            else if(i+1<n){
                dp[i][j]=w[i]-dp[i+1][j];
            }
            else{
                dp[i][j]=w[j]-dp[i][j-1];
            }
        }
    }
    int d=dp[0][n-1];
    printf("%d %d",(sum+d)/2,(sum-d)/2);
    return 0;
}

Python代码:

n=int(input())
total=0
w=[]
while len(w)<n:
    w=w+list(map(int,input().split()))
total=sum(w)
dp=[[0 for _ in range(110)] for _ in range(110)]
for l in range(1,n+1):
    i=0
    while i+l-1<n:
        j=i+l-1
        if i+1<n and j-1>=0:
            dp[i][j]=max(w[i]-dp[i+1][j],w[j]-dp[i][j-1])
        elif i+1<n:
            dp[i][j]=w[i]-dp[i+1][j]
        else:
            dp[i][j]=w[j]-dp[i][j-1]
        i+=1
d=dp[0][n-1]
print(int((total+d)/2),int((total-d)/2))


网站公告

今日签到

点亮在社区的每一天
去签到