jzoj2642. 【NOIP2011模拟10.31】游戏

Description

Alice和Bob在玩一个游戏，游戏是在一个N*N的矩阵上进行的，每个格子上都有一个正整数。当轮到Alice/Bob时，他/她可以选择最后一列或最后一行，并将其删除，但必须保证选择的这一行或这一列所有数的和为偶数。如果他/她不能删除最后一行或最后一列，那么他/她就输了。两人都用最优策略来玩游戏，Alice先手，问Alice是否可以必胜？

Input

第一行：T，表示数据组数
对于每组数据的第一行：N
接下来N行，每行N个数，描述这个矩阵

Output

如果Alice必胜输出W，否则输出L

Sample Input

2
2
2 4
6 8
3
5 4 2
1 5 9
7 3 8

Sample Output

L
W

Data Constraint

Hint

100%数据满足
1<=N<=1000
保证每一行或每一列的和不会超过2*10^9
1<=T<=5

30%数据满足
1<=N<=5

50%数据满足
1<=N<=100

70%数据满足
1<=N<=500

正解

矩形DP

lie[i,j]代表列的前缀和

hang[i,j]代表行的前缀和

dp[i,j,k]代表递归到i，j这个点时 横切/竖切 的dp值（必胜/必输）

p[i,j,k]代表这种状态是否走过

倒推上去，枚举两种情况

本蒟解释不清，自行看biao。。。

CODE

var
        p,dp:array[0..2000,0..2000,0..1]of boolean;
        lie,hang,map:array[0..2000,0..2000]of longint;
        i,j,t,n:longint;
function dfs(i,j,k:longint):boolean;
begin
        if (i=0)or(j=0) then exit(false);
        if (p[i,j,k]) then exit(dp[i,j,k]);
        if (hang[i,j] mod 2=0) then
                dp[i,j,k]:=not(dfs(i-1,j,k xor 1));
        if (lie[i,j] mod 2=0) then begin
                if (not dfs(i,j-1,k xor 1))or(dp[i,j,k]) then
                        dp[i,j,k]:=true
                else
                        dp[i,j,k]:=false;
        end;
        p[i,j,k]:=true;
        exit(dp[i,j,k]);
end;
begin
        readln(t);
        while t<>0 do begin
                fillchar(hang,sizeof(hang),0);
                fillchar(lie,sizeof(lie),0);
                fillchar(p,sizeof(p),false);
                fillchar(dp,sizeof(dp),false);
                readln(n);
                for i:=1 to n do
                        for j:=1 to n do begin
                                read(map[i,j]);
                                hang[i,j]:=hang[i,j-1]+map[i,j];
                                lie[i,j]:=lie[i-1,j]+map[i,j];
                        end;
                if dfs(n,n,0) then
                        writeln('W')
                else
                        writeln('L');
                dec(t);
        end;
end.