题目链接：https://www.luogu.org/problemnew/show/P4363
分析：
首先博弈，然后考虑棋盘的规则，因为一个子在落下时它的上面和左面都已经没有空位了，所以棋子的右下的轮廓线一定是个凸包，更具体地，从棋盘的左下沿着棋盘边界或棋子轮廓线走到棋盘右上，所走的路径一定只有向上和向右两种。
代码：
#include<cstdio>
using namespace std
;
const int maxn
=25,N
=1<<20,INF
=0x3f3f3f3f;
int f
[N
],n
,m
,nm
,c
[2][maxn
][maxn
];bool vis
[N
];
void Max(int &x
,int y
)
{
if(x
<y
)
x
=y
;
}
int Run(int now
,bool rt
)
{
if(vis
[now
])
return -f
[now
];
vis
[now
]=true;
int &ans
=f
[now
],k
=0,i
,j
,cur
=now
,cnt
=0;
ans
=-INF
;
for(k
=0;now
&&(k
<nm
);k
++,cnt
+=i
)
{
i
=now
&1,now
>>=1,j
=now
&1;
if(i
&&!j
)
Max(ans
,Run(cur
^(3<<k
),!rt
)+c
[rt
][k
+1-cnt
][m
-cnt
]);
}
return -ans
;
}
int main()
{
int i
,j
;
scanf("%d%d",&n
,&m
),nm
=n
+m
-1;
for(i
=1;i
<=n
;i
++)
for(j
=1;j
<=m
;j
++)
scanf("%d",&c
[0][i
][j
]);
for(i
=1;i
<=n
;i
++)
for(j
=1;j
<=m
;j
++)
scanf("%d",&c
[1][i
][j
]);
vis
[((1<<m
)-1)<<n
]=true,printf("%d\n",-Run((1<<m
)-1,0));
return 0;
}
转载于:https://www.cnblogs.com/vercont/p/10210025.html
相关资源：JAVA上百实例源码以及开源项目
