首页 > 代码库 > noi-openjudge[4.7搜索]怀表问题

noi-openjudge[4.7搜索]怀表问题

2024-08-19 23:33:07   220人阅读

为啥我觉得这是个DP….f[i][j][k][l]表示四种零件分别用了i,j,k,l个的方案数。然后发现这样不能保证表一定能接在表链首尾，也不知道状态之间如何转移，那么加一维变成f[i][j][k][l][S],S表示首尾的状态(4种),于是就可以预处理了。然后我们需要从给出的一共n个4种零件中选出k个。那么dfs暴力枚举方案。

一开始DP求的状态是i,j,k,l四维都取到1-40，算了一些冗余状态,T了……后来限制四维之和小于等于40,A了……不过慢死…好像别人是直接搜的，加个记忆化?因为真正用到的状态数目不多所以会比较快?

#include<cstdio>
typedef long long ll;
ll f[45][45][45][45][4];//4:首-尾字母 
void dp(){//并不是所有状态都会被用到？ 
    f[1][0][0][0][0]=f[0][1][0][0][1]=f[0][0][1][0][2]=f[0][0][0][1][3]=1;
    for(int i=0;i<=40;++i){
        for(int j=0;i+j<=40;++j){
            for(int k=0;i+j+k<=40;++k){
                for(int l=0;i+j+k+l<=40;++l){
                    if(i+j+k+l==1)continue;
                    for(int s=0;s<4;++s){
                        if(i!=0&&(s&1)==0)f[i][j][k][l][s]+=f[i-1][j][k][l][s];
                        if(j!=0&&(s&1)==1)f[i][j][k][l][s]+=f[i][j-1][k][l][s^1];
                        if(k!=0&&(s&1)==0)f[i][j][k][l][s]+=f[i][j][k-1][l][s^1];
                        if(l!=0&&(s&1)==1)f[i][j][k][l][s]+=f[i][j][k][l-1][s];
                    }
                } 
            } 
        } 
    }
}
int cnt[4];
int sol[4];
ll ans=0;int S;
int n,k;
void dfs(int x,int sum){
    if(x==4){
        if(sum==0)ans+=f[sol[0]][sol[1]][sol[2]][sol[3]][S];
        return;
    }
    for(int i=0;i<=cnt[x]&&i<=sum;++i){
        sol[x]=i;
        dfs(x+1,sum-i);
        sol[x]=0;
    }
    
}
int main(){
    dp();
    char buf[3];
    while(scanf("%d%d",&n,&k)!=EOF){
        scanf("%s",buf);
        S=0;
        if(buf[0]==‘V‘)S+=1;
        if(buf[1]==‘V‘)S+=2;
        cnt[0]=cnt[1]=cnt[2]=cnt[3]=0;
        for(int i=1;i<=n;++i){
            scanf("%s",buf);
            int tmp=0;
            if(buf[0]==‘V‘)tmp+=2;
            if(buf[1]==‘V‘)tmp+=1;
            cnt[tmp]++;
        }  
        ans=0;
        dfs(0,k);

        if(ans==0)printf("NO\n");
        else printf("YES\n%lld\n",ans);
    }
    return 0;
}

 

noi-openjudge[4.7搜索]怀表问题


联系
我们