[九省联考2018]一双木棋chess

[九省联考2018]一双木棋chess

据说这题是可以暴力踩过去的。。

还是考虑正解吧,是一种叫 轮廓线dp 的只听过没写过的东西

不难发现,最后拿出来的棋子一定是左上角占的一块区域。发现$n + m \leq 20$我们可以状压一下这个区域右上到左下的边界。具体来说,我们存一个$2^{n + m}$以内的数,1 表示向下 0 表示向左。

是否需要再开一维状态维护当前是哪个人在下?没必要,当确定轮廓线的时候已经下的步数是确定的,所以可以知道是谁在下。为了方便实现采用记搜。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
using namespace std;
#define MAXN 12
int n , m;
int A[MAXN][MAXN] , B[MAXN][MAXN];
int dp[1 << 20];
int work( int sta , int w ) {
if( ~dp[sta] ) return dp[sta];
dp[sta] = w ? -0x3f3f3f3f : 0x3f3f3f3f;
int x = n , y = 0;
for( int i = 0 ; i < n + m - 1 ; ++ i ) {
if( sta & ( 1 << i ) ) -- x;
else ++ y;
if( ( ( sta >> i ) & 3 ) != 1 ) continue; // LefT,DowN
// LefT DowN -> DowN LefT
if( w ) dp[sta] = max( dp[sta] , work( sta ^ ( 3 << i ) , w ^ 1 ) + A[x + 1][y + 1] );
else dp[sta] = min( dp[sta] , work( sta ^ ( 3 << i ) , w ^ 1 ) - B[x + 1][y + 1] );
}
return dp[sta];
}
int main() {
cin >> n >> m;
for( int i = 1 ; i <= n ; ++ i ) for( int j = 1 ; j <= m ; ++ j ) scanf("%d",&A[i][j]);
for( int i = 1 ; i <= n ; ++ i ) for( int j = 1 ; j <= m ; ++ j ) scanf("%d",&B[i][j]);
memset( dp , -1 , sizeof dp );
dp[( 1 << n ) - 1 << m] = 0;
cout << work( ( 1 << n ) - 1 , 1 ) << endl;
}
文章作者: yijan
文章链接: https://yijan.co/old1/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yijan's Blog