[JZOJ5749] 小J真爱粉交流群 博弈

时间:2022-06-12 16:19:20

首先不难发现:
B只会在A所在位置下面选择建墙或者不建;
如果选择不建A一定会向下走。
那么就可以推导出B在某一行建的墙一定是A移动的区间。
那么我们设 f i , l , r 表示B在第 i 行的 [ l , r ] 下有墙,A在 l 1 时的分数, g i , l , r 则表示A在 r + 1 的分数。
两者转移类似,我们考虑 f 的转移。
当前是B操作,那么B会选择建墙和不建墙中较大的一个,建墙的话A会选择移动到 l 2 或者 r + 1 中较小的一个,具体地:

f i , l , r = s c o r e i , l 1 + max ( f i + 1 , l , l 1 , min ( f i , l 1 , r , g i , l 1 , r + k = l r s c o r e k ) )

要注意左右边界的特殊情况。
代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#define S(i,j,k) (s[i][k]-s[i][j-1])
#define N 110
using namespace std;
const int inf=0x3f3f3f3f;
int n,m,a[N][N],s[N][N],f[N][N][N],g[N][N][N];
int main()
{
    int ca;
    scanf("%d",&ca);
    while(ca--)
    {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                scanf("%d",&a[i][j]);
        memset(s,0,sizeof(s));      
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                s[i][j]=s[i][j-1]+a[i][j];
        memset(f,0x3f,sizeof(f));
        memset(g,0x3f,sizeof(g));
        for(int j=1;j<=m;j++)
            f[n][j+1][j]=g[n][j][j-1]=a[n][j];      
        for(int i=n-1;i;i--)
            for(int len=m-1;len>=0;len--)
                for(int l=1,r=l+len-1;r<=m;l++,r++)
                {
                    if(l>1) f[i][l][r]=a[i][l-1]+max(f[i+1][l][l-1],(l==2&&r==m)?0:min(l>2?f[i][l-1][r]:inf,r<m?g[i][l-1][r]+S(i,l,r):inf));
                    if(r<m) g[i][l][r]=a[i][r+1]+max(g[i+1][r+1][r],(l==1&&r==m-1)?0:min(r<m-1?g[i][l][r+1]:inf,l>1?f[i][l][r+1]+S(i,l,r):inf));
                }
        int ans=inf;
        for(int j=1;j<=m;j++)
            ans=min(ans,min(f[1][j+1][j],g[1][j][j-1]));
        printf("%d\n",ans);                 
    }
    return 0;
}