P2657 [SCOI2009]windy数
标签：mat math cst namespace names print win abs ring
注意此类要处理前导零的数位DP题，因为如果前面全是0，这一位可以填0和1。
#include
#include
#include
#include
#includeusing 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
评论