这题刚开始理解错题意了 以为只能往右和下走
这题挺好的 看题解看了N久啊
二维的DP 第一维表示走到第几步 可以画一个正方形 以左上角斜着划线 第i步走的点只能是第i条线上的点 而dp的第二维 就表示的第i步可以到达的点的状态
另开一个a数组来表示 第i条线上每个字母的状态
dp所代表的值就为a与b的差值 以这个来进行选择 进行记忆化
确定下一步可以到达的字母的状态 是以当前可达的状态&下一步所要到达的字母的状态
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<vector>
using namespace std;
#define LL __int64
#define INF 1e9
int dp[][<<],a[][];
char s[][];
int n;
int dfs(int step,int sta)
{
int i,num=;
if(dp[step][sta]!=INF)
return dp[step][sta];
for(i = ; i < n ; i++)
{
if(sta&(<<i))
{
if(s[step-i][i]=='a') num++;
else if(s[step-i][i]=='b') num--;
break;
}
}
if(step==*n-)
return dp[step][sta] = num;
if(step%!=)
{
dp[step][sta] = -INF;
for(i = ; i < ; i++)
{
int next = a[step+][i]&(sta|(sta<<));
if(next==)
continue;
dp[step][sta] = max(dp[step][sta],dfs(step+,next)+num);
}
return dp[step][sta];
}
else
{
for(i = ; i < ; i++)
{
int next = a[step+][i]&(sta|(sta<<));
if(next==)
continue;
dp[step][sta] = min(dp[step][sta],dfs(step+,next)+num);
}
return dp[step][sta];
}
}
int main()
{
int i,j;
scanf("%d",&n);
for(i = ; i < n ; i++)
cin>>s[i];
for(i = ; i < *n- ; i++)
{
for(j = ; j < n ; j++)
{
if(i-j<||i-j>=n) continue;
a[i][s[i-j][j]-'a'] |= (<<j);
}
}
for(i = ; i < *n ; i++)
for(j = ; j < (<<n) ; j++)
dp[i][j] = INF;
int ans = dfs(,);
if(ans>)
puts("FIRST");
else if(ans<)
puts("SECOND");
else
puts("DRAW");
return ;
}