P2518 [HAOI2010] 计数 题解

· · 题解

思路

一眼数位 DP。

很显然，我们不会想到直接写上 DP，而是写更好写的记忆化搜索。我们定义 \mathit{f}_{now,a,b,c,d,e,f,g,h,i,j} 表示搜索到第 i 位，0 到 9 的出现次数对应 a 到 j 时的答案。但这是一个 11 维的数组，每个数字出现的次数都在 0 到 50 之间，所以，我们 f 数组需要的内存为：50^{11}，爆炸了。所以考虑开一个 11 维的 map 来存，并加以卡常，得到 80 分代码，如下：

#include<bits/stdc++.h>
using namespace std;
short len,a[51];
string s;
map<short,map<short,map<short,map<short,map<short,map<short,map<short,map<short,map<short,map<short,map<short,long long>>>>>>>>>>> F; 
short cnt[10];//存每个数字需要出现的次数 
inline long long dfs(short now_where,short if_le,short if_z,short z,short o,short t,short tr,short f,short fi,short s,short se,short e,short ni){
    if(!now_where) return (o==cnt[1]&&t==cnt[2]&&tr==cnt[3]&&f==cnt[4]&&fi==cnt[5]&&s==cnt[6]&&se==cnt[7]&&e==cnt[8]&&ni==cnt[9])?1:0;
    else if(!if_le&&!if_z&&F[now_where][z][o][t][tr][f][fi][s][se][e].count(ni)) return F[now_where][z][o][t][tr][f][fi][s][se][e][ni];
    long long ans=0,up=if_le?a[now_where]:9;
    for(register short i=0;i<=up;++i){
        if(if_z&&i==0) ans+=dfs(now_where-1,if_le&&i==up,1,z,o,t,tr,f,fi,s,se,e,ni);
        else if(i==0&&z +1<=cnt[0]) ans+=dfs(now_where-1,if_le&&i==up,0,z+1,o,t,tr,f,fi,s,se,e,ni);
        else if(i==1&&o +1<=cnt[1]) ans+=dfs(now_where-1,if_le&&i==up,0,z,o+1,t,tr,f,fi,s,se,e,ni);
        else if(i==2&&t +1<=cnt[2]) ans+=dfs(now_where-1,if_le&&i==up,0,z,o,t+1,tr,f,fi,s,se,e,ni);
        else if(i==3&&tr+1<=cnt[3]) ans+=dfs(now_where-1,if_le&&i==up,0,z,o,t,tr+1,f,fi,s,se,e,ni);
        else if(i==4&&f +1<=cnt[4]) ans+=dfs(now_where-1,if_le&&i==up,0,z,o,t,tr,f+1,fi,s,se,e,ni);
        else if(i==5&&fi+1<=cnt[5]) ans+=dfs(now_where-1,if_le&&i==up,0,z,o,t,tr,f,fi+1,s,se,e,ni);
        else if(i==6&&s +1<=cnt[6]) ans+=dfs(now_where-1,if_le&&i==up,0,z,o,t,tr,f,fi,s+1,se,e,ni);
        else if(i==7&&se+1<=cnt[7]) ans+=dfs(now_where-1,if_le&&i==up,0,z,o,t,tr,f,fi,s,se+1,e,ni);
        else if(i==8&&e +1<=cnt[8]) ans+=dfs(now_where-1,if_le&&i==up,0,z,o,t,tr,f,fi,s,se,e+1,ni);
        else if(i==9&&ni+1<=cnt[9]) ans+=dfs(now_where-1,if_le&&i==up,0,z,o,t,tr,f,fi,s,se,e,ni+1);
    }
    if(!if_le&&!if_z) F[now_where][z][o][t][tr][f][fi][s][se][e][ni]=ans;
    return ans;
}
inline void solve(){
    cin>>s;
    for(register short i=s.size()-1;i>=0;--i) a[++len]=s[i]-'0',++cnt[s[i]-'0'];
    printf("%lld",dfs(len,1,1,0,0,0,0,0,0,0,0,0,0)-1);
}
int main(){
    solve();
    return 0;
}

考虑优化掉 a 到 k 的部分。继续我们用 map 的想法，不难想到将 a 到 k 的部分拼起来，使其成为一个字符串。这样的话我们就只需要开一个 2 维的 map 数组了，大大节省了空间和时间的复杂度。

如何将 a 到 k 的部分拼成字符串？如果我们直接就单纯地把 a 到 k 的值首尾连接的话，可能出现这种情况：分不清哪个数字对应的值是什么，比如 a=10,b=11，单纯连接就是 1011，在不知道 a,b 的值的情况下单看这个字符串是看不懂的。所以，我们需要用一些特殊的字符来区分它们。在这里，我选择的是逗号，将逗号加在每个值的后面。这样能很轻松看出每个数字出现的次数且不会出错。

我们写一个函数，便于计算某些值用这种方法转化成字符串，在每一次搜索完成后，只需要判断该情况与目标字符串是否相等即可。

注：这里有一个剪枝，就是在一个数字出现的次数大于目标出现次数的时候，我们是可以放弃这种情况的搜索的。

代码

#include<bits/stdc++.h>
using namespace std;
short len,a[51],cnt[10];
string s,all;
map<short,map<string,long long>> F; 
inline string get(short o,short t,short tr,short f,short fi,short s,short se,short e,short ni){
    string nowk="";short w;
    w=o ;while(w) nowk+=(w%10+'0'),w/=10;nowk+=',';//加区分的字符 
    w=t ;while(w) nowk+=(w%10+'0'),w/=10;nowk+=',';
    w=tr;while(w) nowk+=(w%10+'0'),w/=10;nowk+=',';
    w=f ;while(w) nowk+=(w%10+'0'),w/=10;nowk+=',';
    w=fi;while(w) nowk+=(w%10+'0'),w/=10;nowk+=',';
    w=s ;while(w) nowk+=(w%10+'0'),w/=10;nowk+=',';
    w=se;while(w) nowk+=(w%10+'0'),w/=10;nowk+=',';
    w=e ;while(w) nowk+=(w%10+'0'),w/=10;nowk+=',';
    w=ni;while(w) nowk+=(w%10+'0'),w/=10;nowk+=',';
    return nowk;
}
inline long long dfs(short now_where,bool if_le,bool if_z,short z,short o,short t,short tr,short f,short fi,short s,short se,short e,short ni,string now){
    if(!now_where) return now==all;
    if(!if_le&&!if_z&&F[now_where].count(now)) return F[now_where][now];
    long long ans=0,up=if_le?a[now_where]:9;
    for(register short i=0;i<=up;++i){
        if(if_z&&i==0)ans+=dfs(now_where-1,if_le&&i==up,1,0,0,0,0,0,0,0,0,0,0,"");
        else if(i==0) ans+=dfs(now_where-1,if_le&&i==up,0,z+1,o,t,tr,f,fi,s,se,e,ni,now);
        else if(i==1&&o +1<=cnt[1]) ans+=dfs(now_where-1,if_le&&i==up,0,z,o+1,t,tr,f,fi,s,se,e,ni,get(o+1,t,tr,f,fi,s,se,e,ni));        
        else if(i==2&&t +1<=cnt[2]) ans+=dfs(now_where-1,if_le&&i==up,0,z,o,t+1,tr,f,fi,s,se,e,ni,get(o,t+1,tr,f,fi,s,se,e,ni));
        else if(i==3&&tr+1<=cnt[3]) ans+=dfs(now_where-1,if_le&&i==up,0,z,o,t,tr+1,f,fi,s,se,e,ni,get(o,t,tr+1,f,fi,s,se,e,ni));
        else if(i==4&&f +1<=cnt[4]) ans+=dfs(now_where-1,if_le&&i==up,0,z,o,t,tr,f+1,fi,s,se,e,ni,get(o,t,tr,f+1,fi,s,se,e,ni));
        else if(i==5&&fi+1<=cnt[5]) ans+=dfs(now_where-1,if_le&&i==up,0,z,o,t,tr,f,fi+1,s,se,e,ni,get(o,t,tr,f,fi+1,s,se,e,ni));
        else if(i==6&&s +1<=cnt[6]) ans+=dfs(now_where-1,if_le&&i==up,0,z,o,t,tr,f,fi,s+1,se,e,ni,get(o,t,tr,f,fi,s+1,se,e,ni));
        else if(i==7&&se+1<=cnt[7]) ans+=dfs(now_where-1,if_le&&i==up,0,z,o,t,tr,f,fi,s,se+1,e,ni,get(o,t,tr,f,fi,s,se+1,e,ni));
        else if(i==8&&e +1<=cnt[8]) ans+=dfs(now_where-1,if_le&&i==up,0,z,o,t,tr,f,fi,s,se,e+1,ni,get(o,t,tr,f,fi,s,se,e+1,ni));
        else if(i==9&&ni+1<=cnt[9]) ans+=dfs(now_where-1,if_le&&i==up,0,z,o,t,tr,f,fi,s,se,e,ni+1,get(o,t,tr,f,fi,s,se,e,ni+1));
    }
    if(!if_le&&!if_z) F[now_where][now]=ans;
    return ans;
}
inline void solve(){
    cin>>s;
    for(register short i=s.size()-1;i>=0;--i) a[++len]=s[i]-'0',++cnt[s[i]-'0'];
    all=get(cnt[1],cnt[2],cnt[3],cnt[4],cnt[5],cnt[6],cnt[7],cnt[8],cnt[9]); 
    printf("%lld",dfs(len,1,1,0,0,0,0,0,0,0,0,0,0,"")-1);//-1是减去的s这种情况，因为我们求的值s之前的数的个数
}
int main(){
    solve();
    return 0;
}

注：虽然上面的代码比 @WaterSun 的长一些，但是用时和内存都更优哦。