LINK

A l i c e Alice Alice和 B o b Bob Bob做游戏,轮流操作一个 01 01 01串

操作分为一下两种

Ⅰ.花费 1 1 1块钱把 s [ i ] = 0 s[i]=0 s[i]=0修改为 s [ i ] = 1 s[i]=1 s[i]=1

Ⅱ.如果上一次操作不是翻转且这个串不是回文串,花费 0 0 0块钱把整个串翻转

当整个串变成全 1 1 1时游戏结束,求最后谁花的钱少

---

显然有一个很无脑的记忆化搜索

发现操作二需要判断当前是否是回文,也就是判断 a i a_i ai​和 a n − i + 1 a_{n-i+1} an−i+1​是什么样的

有三种形态,分别是 00 , 11 , 01 / 10 00,11,01/10 00,11,01/10

其中 11 11 11是没有用的,既不影响判断回文,又不会被操作

所以定义 f [ q ] [ w ] [ e ] [ r ] f[q][w][e][r] f[q][w][e][r]表示当前有 q q q个形如 01 / 10 01/10 01/10的状态, w w w个形如 00 00 00的状态

e e e表示上一次操作是否是翻转, r r r表示串中间是否是 0 0 0(主要是因为串长奇数时中间是独立的状态)

预处理时间复杂度 O ( ( n 2 ) 2 ∗ 2 2 ) O((\frac{n}{2})^2*2^2) O((2n​)2∗22)

#include <bits/stdc++.h>
using namespace std;
int t,n,f[509][509][2][2];
char a[3009];
int dfs(int q,int w,int e,int r)
{
	if( f[q][w][e][r]!=-1 )	return f[q][w][e][r];
	int ans = 1e9, now = q+w*2+( r==0 );
	if( r==0 )	ans = min( ans,now-dfs(q,w,0,1) );
	if( e==0 && q )	ans = min( ans,now-dfs(q,w,1,r) );	
	if( q )	ans = min( ans,now-dfs(q-1,w,0,r) );
	if( w )	ans = min( ans,now-dfs(q+1,w-1,0,r) );
	return f[q][w][e][r] = ans;
}
int main()
{
	memset( f,-1,sizeof f );
	f[0][0][0][1] = f[0][0][1][1] = 0;
	int t; cin >> t;
	while( t-- )
	{
		scanf("%d%s",&n,a+1 );
		int q = 0, w = 0, e = 0, r = 1, now = 0;
		for(int i=1;i<=n;i++)	now += ( a[i]=='0' );
		for(int i=1;i<=n/2;i++)
		{
			if( (a[i]-'0')+(a[n-i+1]-'0')==1 )	q++;
			if( (a[i]-'0')+(a[n-i+1]-'0')==0 )	w++;
		}
		if( (n&1) && a[n/2+1]=='0' )	r = 0;
		if( dfs(q,w,e,r)<now-dfs(q,w,e,r) )	printf("ALICE\n");
		else if( dfs(q,w,e,r)>now-dfs(q,w,e,r) )	printf("BOB\n");
		else	printf("DRAW\n");
	}
}