首页 > 代码库 > poj:1850 Code(组合数学?数位dp!)
poj:1850 Code(组合数学?数位dp!)
题目大意:字符的字典序依次递增才是合法的字符串,将字符串依次标号如:a-1 b-2 ... z-26 ab-27 bc-52。
为什么题解都是组合数学的...我觉得数位dp很好写啊(逃
f[pos][pre]前pos位,前一位是pre有几个满足条件的字符串,其实等同于这个字符串的序号是多少
好像数位dp的博客真没什么东西好写的...
#include<iostream> #include<cstring> #include<cstdlib> #include<cstdio> using namespace std; char s[20]; int dp[20][50],a[20]; int dfs(int pos,int pre,bool lead,bool limit) { if(pos==0) if(lead)return 0;else return 1; if(!limit && dp[pos][pre]!=-1)return dp[pos][pre]; int up=limit?a[pos]:26; int ans=0,i; if(lead)i=pre;else i=pre+1; for(;i<=up;i++) ans+=dfs(pos-1,i,lead && i==0,limit && i==a[pos]); if(!limit)dp[pos][pre]=ans; return ans; } int solve() { int pos=0; for(int i=0;i<strlen(s)-1;i++) if(s[i]>=s[i+1])return 0; for(int i=strlen(s)-1;i>=0;i--) a[++pos]=s[i]-‘a‘+1; return dfs(pos,0,1,1); } int main() { memset(dp,-1,sizeof(dp)); scanf("%s",s); printf("%d\n",solve()); }
poj:1850 Code(组合数学?数位dp!)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。