BZOJ5248[2018多省省队联测]一双木棋

题目传送门

方法一

看完题目,觉得这是一个神奇的博弈论题目,不会做……然后,看了一眼数据范围,n,m<=10?!好像可以暴力DP啊?来算一下可能的状态数量,同一行中放棋子的点一定是最左边的若干个,令A[i]表示第i行左边的A[i]个格子里放了棋子,根据题目要求不难发现这些性质:m>=A[1]>=A[2]>=A[3]>=…>=A[n-2]>=A[n-1]>=A[n]>=0,可以算出状态A[1~n]只有${n+m+1}\choose{m+1}$个,也就最多只有352716,可以放心的DP。

code:

方法二

事实上,两种方法是本质相同的。

考虑只记下填的数的右下部分的轮廓线。
如果棋盘:(*表示填了数,.表示没填)

那么这条轮廓线是长这样的(从右上角开始):

如果用1表示|,0表示-,那么轮廓线可以表示为(从右上角开始):
0001100100
而每次填一个数,都可以使轮廓线的01变为10。
就能直接转移了。状态数也是${n+m}\choose{n}$个,即这个01序列中恰好有n个1,m个0。
由于状态比较清楚,不需要上面那样毒瘤地 map<vector<int>,int>,所以跑得飞快。传说中在BZOJ上跑了第三。
Code:

2 条评论
  1. 状态数应该是C(n+m,n)

    1. 我也是这么想的,可惜球王说是C(n+m+1,n+1),我也没办法。

发表一条评论