AT_tdpc_game题解

Kketchup · 2023-05-22 22:12:15 · 题解

AT-tdpc-game

传送门

题意简述

Alice 和 Bob 在玩游戏。初始时有两座山，左边的山上有 A 个物品，从上到下的第 i 个价值为 a_i；右边的山上有 B 个物品，从上到下的第 i 个价值为 b_i。Alice 先手，Alice 和 Bob 交替进行操作，可行的操作如下：

如果两座山都空了，游戏结束。
如果只有某一座山空了，取走另一座山上的最上面的物品。
如果两座山都没有空，选择任意一座山，并取走其最上面的物品。

假设两人都采取最优策略，请求出 Alice 能取得的物品的价值总和。

题目解析

与 AT-dp-l 类似。

设 f_{i,j}表示 A 山（从上到下）取到 i，B 山（从上到下）取到 j，Alice 的最大价值总和，则答案为 f_{1,1}。

转移，若轮到 Alice，即 (i+j)\bmod2=0，

f_{i,j}=\max(f_{i+1,j}+a_i,f_{i,j+1}+b_j)

否则 f_{i,j}=\min(f_{i+1,j},f_{i,j+1})

再考虑当 i=n 或者 j=m，即一座山已空，此时在两山情况取一种，可用三目运算简化式子。

if((i+j)%2==0) 
    f[i][j]=max((i==n+1)?0:(f[i+1][j]+a[i]),(j==m+1)?0:(f[i][j+1]+b[j]));
else 
    f[i][j]=min((i==n+1)?INF:f[i+1][j],(j==m+1)?INF:f[i][j+1]);

当然，也可以将两座山拼起来，山顶朝外，注意判断一山取完的情况即可。此处不再详细说明。

具体实现

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int N=1005;
const int INF=0x3f3f3f3f;
int n,m;
int a[N],b[N];
int f[N][N];

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i) scanf("%d",&a[i]);
    for(int i=1;i<=m;++i) scanf("%d",&b[i]);
    for(int i=n+1;i>=1;--i){
        for(int j=m+1;j>=1;--j){
            if(i==n+1&&j==m+1) continue;
            if((i+j)%2==0)
                f[i][j]=max((i==n+1)?0:(f[i+1][j]+a[i]),(j==m+1)?0:(f[i][j+1]+b[j]));
            else
                f[i][j]=min((i==n+1)?INF:f[i+1][j],(j==m+1)?INF:f[i][j+1]);
        }
    }
    printf("%d\n",f[1][1]);
    return 0;
}

完结撒花！请管理通过啦。