首页 > 代码库 > Bzoj1072--Scoi2007排列perm

Bzoj1072--Scoi2007排列perm

2024-08-16 05:29:00   218人阅读

一开始sb以为是数位dp，想到状态是十维每维代表每个数字出现次数，再加一维代表余数。空间时间都要炸飞。。。

后来想了想可以直接用数字在原串上出现的位置来代替那十维，结果没有意识到这就是状压dp。。。导致写出来常数爆炸

不过过了就懒得改了。- -

代码看看就可以了：

#include<bits/stdc++.h>#define LL long long#define MAXN 20000005using namespace std;int dp[15][1030][1005],d,T;int len,full;char s[15];int check(int v,int st) {    for(int i=0;i<len;i++) {        if(s[i]==v&&!(st&(1<<i))) return i;    }    return -1;}int mdp() {    for(int t,i=0;i<=9;i++) {        if((t=check(i+‘0‘,0))!=-1) dp[1][1<<t][i%d]++;    }    for(int i=2;i<=len;i++) {        for(int st=0;st<full;st++)             for(int k=0;k<d;k++) {                if(!dp[i-1][st][k]) continue;                for(int t,j=0;j<=9;j++) {                    if((t=check(j+‘0‘,st))!=-1) dp[i][st|(1<<t)][(k*10+j)%d]+=dp[i-1][st][k];                }            }    }    return dp[len][full-1][0];}int main() {    scanf("%d",&T);    for(int i=1;i<=T;i++) {        scanf("%s%d",s,&d);        memset(dp,0,sizeof(dp));        len=strlen(s);full=1<<len;        printf("%d\n",mdp());    }    return 0;}

 

Bzoj1072--Scoi2007排列perm


联系
我们