P2657 [SCOI2009]windy数
2021-03-20 20:26
阅读:485
标签:mat math cst namespace names print win abs ring
注意此类要处理前导零的数位DP题,因为如果前面全是0,这一位可以填0和1。
#include#include #include #include #include using namespace std; int dp[20][20],num[20]; inline int dfs(int now,int pre,bool limit) { if(now==0) return 1; if(dp[now][pre]!=-1&&!limit) return dp[now][pre]; int ans=0,up=9; if(limit) up=num[now]; for(register int i=0;ii) { if((abs(i-pre))2) continue; if(i==0&&pre==-10) ans+=dfs(now-1,-10,limit&&(i==num[now])); else ans+=dfs(now-1,i,limit&&(i==num[now])); } if(!limit) dp[now][pre]=ans; return ans; } inline int solve(int k) { memset(dp,-1,sizeof(dp)); int pos=0; while(k>0) { num[++pos]=k%10; k/=10; } return dfs(pos,-10,true); } int main() { int x,y; scanf("%d%d",&x,&y); printf("%d\n",solve(y)-solve(x-1)); return 0; }
P2657 [SCOI2009]windy数
标签:mat math cst namespace names print win abs ring
原文地址:https://www.cnblogs.com/Hoyoak/p/11840144.html
文章来自:搜素材网的编程语言模块,转载请注明文章出处。
文章标题:P2657 [SCOI2009]windy数
文章链接:http://soscw.com/index.php/essay/66860.html
文章标题:P2657 [SCOI2009]windy数
文章链接:http://soscw.com/index.php/essay/66860.html
评论
亲,登录后才可以留言!