比赛 | Hexo

归档于 2019-11-09 08:30

我竟然浪费一下午改题时间做了这个sb题

从2.00改到6.00

搜索题还要看代码

我是不是废了

记忆化,但怎么记忆化,记忆化划分状态不太好划分,你不知道哪些队比过了,哪些队没有比过

也就是只拿一些队得分情况划分状态表示不全

我们不能搜到一个状态,记录,return,因为会出现当前本应非法但你取用了记忆化的值就错了

有一种做法就是再记录队之间比赛过状态,然而空间不够

因为任意两支队伍都要比赛一场我们可以列出来比赛是下三角类型的,

队伍1 2 3 4

1 1 1 1 1

2 1 1 1

3 1 1

1 1

枚举当前比赛队伍和枚举的队伍,(拿4举例就是枚举1 2 3和4比赛,然后向前推进到3,枚举1 2 和3比赛,向前推进到2,枚举1和2比赛,最后推进到1)

这样我们dp定义f[x][state]表示推进到第x列,当前球队得分状态是state的得分,有多少种合法方案,这样我们可以间接知道比赛情况

依然会炸内存,但是可以hash表维护

当我们搜完一列时看有没有记忆化,如果没有记忆化就接着搜完下一列

再加一些剪枝

可行性剪枝

如果当前还剩x场比赛,球队i分数a[i],即使x场比赛全赢都得不了a[i]分就return

搜索顺序剪枝

sort排序

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define A 12
const ll modd=1e9+7;
pair<ll,ll> e[A*A];
ll a[A];
ll n,cnt,ans;
struct Hash_Table{
    #define mod 1030829
    ll nxt[mod],val[mod],ver[mod],head[mod];
    ll tot;
    ll &operator [](const ll &H){
        ll x=H%mod;
        for(ll i=head[x];i;i=nxt[i]){
            if(ver[i]==H) return val[i];
        }
        nxt[++tot]=head[x];
        ver[tot]=H;
        head[x]=tot;
        return val[tot];
    }
}H;

ll cmp(ll x,ll y){return x>y;}
ll gethash(ll x){
    ll tmp[11],hh=x;
    for(ll i=1;i<=x;i++)
        tmp[i]=a[i];
    sort(tmp+1,tmp+x+1);
    for(ll i=1;i<=x;i++)
        hh=hh*28+tmp[i];
    return hh;
}
ll dfs(ll x,ll pla){
    if(a[pla]>(pla-x)*3) return 0;
    if(x==pla){
        if(pla==1) return 1;
        else {
            ll hh=gethash(pla-1);
            if(H[hh]!=-1) {
//                printf("h=%lld \n",hh);
                return H[hh];
            }
            else return H[hh]=dfs(1,pla-1);
        }
    }
    ll d=0;
    if(a[x]>=3){
        a[x]-=3;
        d+=dfs(x+1,pla);        if(d>=modd) d-=modd;    
        a[x]+=3;
    }
    if(a[pla]>=3){
        a[pla]-=3;
        d+=dfs(x+1,pla);        if(d>=modd) d-=modd;    
        a[pla]+=3;
    }
    if(a[x]>=1&&a[pla]>=1){
        a[x]--,a[pla]--;
        d+=dfs(x+1,pla);        if(d>=modd) d-=modd;    
        a[x]++,a[pla]++;
    }
    return d;
}
int main(){
    memset(H.val,-1,sizeof(H.val));
    scanf("%lld",&n);
    for(ll i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    sort(a+1,a+n+1,cmp);
    printf("%lld\n",dfs(1,n)%modd);
}

View Code

csps退役前,我最后悔的事就是做了这个sb题