EOJ 140 【神仙互掐】题解

这道题的思路并不难，就是DFS+强剪枝。

没什么好说的，直接粘代码。



我不会告诉你这是BZOJ 1306改题面

#include<iostream>
#include<cstdio>
using namespace std;
int n,a[10],sum,ying,ping;
long long ans;
inline void dfs(int u,int v)
{
    if(u==n&&v==n+1)
    {
        ans++;
        return;
    }
    if(ying>0&&(a[u]>=3||a[v]>=3))
    {
        ying--;
        if(a[u]>=3)
        {
            a[u]-=3;
            if(v!=n)
                dfs(u,v+1);
            else
                if(a[u]==0)
                    dfs(u+1,u+2);
            a[u]+=3;
        }
        if(a[v]>=3)
        {
            a[v]-=3;
            if(v!=n)
                dfs(u,v+1);
            else
                if(a[u]==0)
                    dfs(u+1,u+2);
            a[v]+=3;
        }
        ying++;
    }
    if(ping>0&&a[u]>=1&&a[v]>=1)
    {
        ping--;
        a[u]-=1;
        a[v]-=1;
        if(v!=n)
            dfs(u,v+1);
        else
            if(a[u]==0)
                dfs(u+1,u+2);
        a[u]+=1;
        a[v]+=1;
        ping++;
    }
    return;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;++i)
    {
        cin>>a[i];
        sum+=a[i];
    }
    ying=sum-n*(n-1);
    ping=n*(n-1)/2-ying;
    dfs(1,2);
    cout<<ans;
    return 0;
}