bzoj千题计划294：bzoj3139: [Hnoi2013]比赛

http://www.lydsy.com/JudgeOnline/problem.php?id=3139

队伍的顺序不会影响结果

将队伍的得分情况作为状态，记忆化搜索

就是先搜索第一只队伍的得分情况，即为他分配分数

当第一只队伍的分数分配完时，它与其他队伍的比拼会使其他队伍也分配到了一定的分数

将其他队伍分配到的分数 这个状态 哈希

然后第二支队……，这就是子问题

啊啊啊，我也不知道我在说啥了

myl考场AC tql！！！

#include<algorithm>

#include<cstring>

#include<cstdio>

#include<map>

#define N 11

using namespace std;

typedef long long LL;

const int mod=1e9+;

int n,w[N];

map<LL,int>mp[N];

LL gethash(int *b,int p)

{

    LL S=;

    for(int i=p;i<=n;++i) S=S*+b[i];

    return S;

}

int dfs(int *val,int l,int r)

{

    if(l==r)

    {

        if(val[l]) return ;

        if(l==n) return ;

        int b[N];

        memcpy(b,val,sizeof(b));

        sort(b+l+,b+n+);

        LL S=gethash(b,l+);

        if(mp[l+].find(S)==mp[l+].end()) mp[l+][S]=dfs(b,l+,n);

        return mp[l+][S];

    }

    if(*(r-l)<val[l]) return ;

    int tot=;

    if(val[l]>=)

    {

        val[l]-=;

        tot+=dfs(val,l,r-);

        tot-=tot>=mod ? mod : ;

        val[l]+=;

    }

    if(val[l] && val[r])

    {

        val[l]--; val[r]--;

        tot+=dfs(val,l,r-);

        tot-=tot>=mod ? mod : ;

        val[l]++; val[r]++;

    }

    if(val[r]>=)

    {

        val[r]-=;

        tot+=dfs(val,l,r-);

        tot-=tot>=mod ? mod : ;

        val[r]+=;

    }

    return tot;

}

int main()

{

    scanf("%d",&n);

    for(int i=;i<=n;++i) scanf("%d",&w[i]);

    printf("%d",dfs(w,,n));

}