标签：10 int abc195 dfs pos num dp

博弈论dp

dp[i][j]表示到了第 i 轮，此时数为j，对 当前的人对 j 数进行操作 1表示T赢，0表示A赢

初始化：dp[n+1][0]=1，T赢的条件，其余memset -1

博弈论dp用记忆化搜索dp

此时dfs( pos , num ) 将向 dfs(pos+1,num*10%7)  或  dfs(pos+1,(pos+1,(num*10+a[pos])%7) 转移

如果此时是 Takahashi 如果 dfs(pos+1,num*10%7) 和 dfs(pos+1,(pos+1,(num*10+a[pos])%7) 只要有一个是T能赢的情况，那么 dfs( pos , num ) 就是T能赢的情况

如果此时是 Aoki 如果 dfs(pos+1,num*10%7) 和 dfs(pos+1,(pos+1,(num*10+a[pos])%7) 只要有一个是A能赢的情况，那么 dfs( pos , num ) 就是A能赢的情况

T轮次：则  dp[pos][num]=dfs(pos+1,num*10%7)||dfs(pos+1,(num*10+a[pos])%7);

 A轮次：则 dp[pos][num]=dfs(pos+1,num*10%7)&&dfs(pos+1,(num*10+a[pos])%7);

从dfs(1,0)开始

Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back   
#define popb pop_back  
#define fi first
#define se second
#define popcount __builtin_popcount
const int N=2e5+10;
//const int M=;
//const int inf=1e9;
//const ll INF=1e18;
int T,n;
int dp[N][8],a[N];
char s1[N];
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*f;
}
bool dfs(int pos,int num)
{
    if(dp[pos][num]!=-1) return dp[pos][num];
    if(pos>n) return 0;
    if(s1[pos]=='A')
    {
        dp[pos][num]=dfs(pos+1,num*10%7)&&dfs(pos+1,(num*10+a[pos])%7);
        return dp[pos][num];
    }
    else
    {
        dp[pos][num]=dfs(pos+1,num*10%7)||dfs(pos+1,(num*10+a[pos])%7);
        return dp[pos][num];
    }
}
int main()
{
//    freopen("","r",stdin);
//    freopen("","w",stdout);
//    ios::sync_with_stdio(0);
//    cin.tie(0);
    n=read();
    for(int i=1;i<=n;i++) scanf("%1d",&a[i]);
    scanf("%s",s1+1);
    memset(dp,-1,sizeof(dp));
    dp[n+1][0]=1;
    if(dfs(1,0)) puts("Takahashi");
    else puts("Aoki");
    return 0;
}

 

 

标签：10,int,abc195,dfs,pos,num,dp
From： https://www.cnblogs.com/Willette/p/17307926.html