bzoj 1026 [ SCOI2009 ] windy数 —— 数位DP
标签：++ blank code https php geo iostream bsp 为什么
题目：https://www.lydsy.com/JudgeOnline/problem.php?id=1026
蛮简单的数位DP，预处理 f[i][j] 表示 i 位数，以 j 开头的 windy 数个数；
但不明白为什么最后一位拿出来特判 ret++ 不对，而写在循环里，特判 i==1 就对了...
代码如下：
#include
#include
#include
#include
using namespace std;
int a,b,f[15][15],num[15];
int abb(int x){return (x>0)?x:-x;}
int getnum(int x)
{
int cnt=0;
while(x)num[++cnt]=x%10,x/=10;
return cnt;
}
void init()
{
int mx=getnum(b);
for(int i=0;i9;i++)f[1][i]=1;
for(int i=2;i)
for(int j=0;j9;j++)
for(int k=0;k9;k++)
if(abb(j-k)>=2)f[i][j]+=f[i-1][k];
}
int calc(int x)
{
int mx=getnum(x),ret=0;
for(int i=1;i)
for(int j=1;j9;j++)ret+=f[i][j];
for(int j=1;jf[mx][j];
for(int i=mx-1,pre;i;i--)
{
pre=num[i+1];
if(i!=1)
{
for(int j=0;j)
if(abb(pre-j)>=2)ret+=f[i][j];
}
if(i==1)//AC
{
for(int j=0;j)
if(abb(pre-j)>=2)ret+=f[i][j];
}
if(abb(num[i]-pre)2)break;//!
}
// if(mx==1||abb(num[1]-num[2])>=2)ret++;//WA
// if(abb(num[1]-num[2])>=2)ret++;//WA
return ret;
}
int main()
{
scanf("%d%d",&a,&b);
init();
printf("%d\n",calc(b)-calc(a-1));
return 0;
}
bzoj 1026 [ SCOI2009 ] windy数 —— 数位DP
标签：++ blank code https php geo iostream bsp 为什么
原文地址：https://www.cnblogs.com/Zinn/p/9395042.html
评论