「Luogu4363/BZOJ5248」[九省联考2018]一双木棋chess

学校省选模拟居然拿九省联考来考

然而我还是too youngtoo\space young，搞不懂什么叫最优

让二者的答案最接近可以拿到2525分的好成绩

problem

Solution

首先可以知道菲菲想要最大化ans=Ansa−Ansbans=Ansa-Ansb，牛牛想要最小化

那么我们可以用对抗搜索大力爆搜

可以拿到50分

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long ll;

template <typename T> void read(T &t)
{
    t=0;int f=0;char c=getchar();
    while(!isdigit(c)){f|=c=='-';c=getchar();}
    while(isdigit(c)){t=t*10+c-'0';c=getchar();}
    if(f)t=-t;
}

const int maxn=15,maxm=15;
int n,m;
int A[maxn][maxm],B[maxn][maxm];
int ocr[maxn][maxm];

int dfs(int step)
{
    if(step==n*m+1)
        return 0;
    int re=0;
    if(step&1)re=-0x3f3f3f3f;
    else re=0x3f3f3f3f;
    for(register int i=1;i<=n;++i)
        for(register int j=1;j<=m;++j)
            if(!ocr[i][j] && ocr[i-1][j] && ocr[i][j-1])
            {
                ocr[i][j]=1;
                if(step&1)re=max(re,dfs(step+1)+A[i][j]);
                else re=min(re,dfs(step+1)-B[i][j]);
                ocr[i][j]=0;
            }
    return re;
}

int main()
{
    read(n);read(m);
    for(register int i=1;i<=n;++i)
        for(register int j=1;j<=m;++j)
            read(A[i][j]);
    for(register int i=1;i<=n;++i)
        for(register int j=1;j<=m;++j)
            read(B[i][j]);
    for(register int i=0;i<=n;++i)ocr[i][0]=1;
    for(register int i=0;i<=m;++i)ocr[0][i]=1;
    printf("%d",dfs(1));
    return 0;
}

显然这个东西可以记忆化一下

用mapmap存一下棋盘的哈希值，吸氧的情况下是能A掉的

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

template <typename T> void read(T &t)
{
    t=0;int f=0;char c=getchar();
    while(!isdigit(c)){f|=c=='-';c=getchar();}
    while(isdigit(c)){t=t*10+c-'0';c=getchar();}
    if(f)t=-t;
}

const int maxn=15,maxm=15;

int n,m;
int A[maxn][maxm],B[maxn][maxm];
int ocr[maxn][maxm];
map<ull,int> rec;

ull Hash()
{
    ull re=0;
    for(register int i=1;i<=n;++i)
        for(register int j=1;j<=m;++j)
            re=re*3ull+ocr[i][j];
    return re;
}

int dfs(int step)
{
    if(step==n*m+1)
        return 0;
    int re=0;
    ull h=Hash();
    if(rec.find(h)!=rec.end())
        return rec[h];
    if(step&1)re=-0x3f3f3f3f;
    else re=0x3f3f3f3f;
    for(register int i=1;i<=n;++i)
        for(register int j=1;j<=m;++j)
            if(!ocr[i][j] && ocr[i-1][j] && ocr[i][j-1])
            {
                ocr[i][j]=1;
                if(step&1)re=max(re,dfs(step+1)+A[i][j]);
                else re=min(re,dfs(step+1)-B[i][j]);
                ocr[i][j]=0;
            }
    return rec[h]=re;
}

int main()
{
    read(n);read(m);
    for(register int i=1;i<=n;++i)
        for(register int j=1;j<=m;++j)
            read(A[i][j]);
    for(register int i=1;i<=n;++i)
        for(register int j=1;j<=m;++j)
            read(B[i][j]);
    for(register int i=0;i<=n;++i)ocr[i][0]=1;
    for(register int i=0;i<=m;++i)ocr[0][i]=1;
    printf("%d",dfs(1));
    return 0;
}

经过百度一下之后，发现此类对抗搜索还有一种优化，叫做Alpha−BetaAlpha-Beta优化

在此仅放上介绍链接，不再赘述

对于此题，我们如果使用Alpha−BetaAlpha-Beta优化，也能获得70分的成绩

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

template <typename T> void read(T &t)
{
	t=0;int f=0;char c=getchar();
	while(!isdigit(c)){f|=c=='-';c=getchar();}
	while(isdigit(c)){t=t*10+c-'0';c=getchar();}
	if(f)t=-t;
}

const int maxn=15,maxm=15;

int n,m;
int A[maxn][maxm],B[maxn][maxm];
int ocr[maxn][maxm];

const int inf=0x3f3f3f3f;


int dfs(int step,int alpha,int beta,int nowa,int nowb)
{
	if(step==n*m+1)
		return nowa-nowb;
	if(step&1)
	{
		for(register int i=1;i<=n;++i)
			for(register int j=1;j<=m;++j)
				if(!ocr[i][j] && ocr[i-1][j] && ocr[i][j-1])
				{
					ocr[i][j]=1;
					alpha=max(alpha,dfs(step+1,alpha,beta,nowa+A[i][j],nowb));
					ocr[i][j]=0;
					if(alpha>=beta)return alpha;
				}
		return alpha;
	}
	else
	{
		for(register int i=1;i<=n;++i)
			for(register int j=1;j<=m;++j)
				if(!ocr[i][j] && ocr[i-1][j] && ocr[i][j-1])
				{
					ocr[i][j]=1;
					beta=min(beta,dfs(step+1,alpha,beta,nowa,nowb+B[i][j]));
					ocr[i][j]=0;
					if(alpha>=beta)return beta;
				}
		return beta;
	}
}

int main()
{
	read(n);read(m);
	for(register int i=1;i<=n;++i)
		for(register int j=1;j<=m;++j)
			read(A[i][j]);
	for(register int i=1;i<=n;++i)
		for(register int j=1;j<=m;++j)
			read(B[i][j]);
	for(register int i=0;i<=n;++i)ocr[i][0]=1;
	for(register int i=0;i<=m;++i)ocr[0][i]=1;
	printf("%d",dfs(1,-inf,inf,0,0));
	return 0;
}