[SCOI2009]windy数
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
写完这道题感觉心好累...这辈子都不想再做数位DP的题了，然而他们说这是道入门题...
首先可以DP得到位数为i，最高位为j的windy数个数g(i,j)
然后对于(0,k)内的windy数个数，可以讨论3种情况：（感觉数位DP就是大讨论..）
（假设总位数为l,假设k的从高到低第t位为bit(t) ）
①最高位为0，位数为[1,l - 1]的windy数个数(Σ(q=1,l-1) Σ(p=1,9) g(p,q))
②最高位为[1,k - 1]，位数为l的windy数个数(Σ(q=1,k-1) g(l,q))
③最高位为k的windy数个数，这个比较复杂，总之是从高位到低位依次确定，伪代码如下：
for i = (len - 1) to 1 , step -1:
for q = 1 to bit(i) - 1 (#) , step 1:
if(|q - bit(i + 1)| > 2)
sum <- sum + g(i,q)
endif
endfor
endfor
注意打#的地方，这里取bit(i) - 1是因为求的是开区间（闭区间的话会麻烦一点）
完整代码如下：
#include <stdio.h>
#include <string.h>
#include <iostream>
typedef long long Long;
Long g[20][20];//g[i][j] : i位开头为j的windy数个数
Long ABS(Long a)
{
return a > (Long)0 ? a : -a;
}
void init()
{
for(Long i = 0;i < 10;i++)
g[1][i] = 1LL;
for(Long i = 2;i <= 10;i++)
{
for(Long j = 0;j < 10;j++)
{
for(Long k = 0;k < 10;k++)
{
if(ABS(j - k) >= 2)
g[i][j] += 1LL * g[i - 1][k];
}
}
}
}
Long bit[20];
Long len = 0;
Long get_res(Long k)//(0,k)
{
memset(bit,0,sizeof(bit));
len = 0;
Long q = k;
while(q)
{
bit[++len] = (q % 10LL);
q /= 10LL;
}
Long result = 0;
/*
000x
00xx
0xxx...
*/
for(Long i = 1;i < len;i++)
{
for(Long j = 1;j < 10LL;j++)
{
result += 1LL * g[i][j];//开头不可为0
}
}
/*
1xxx
2xxx
3xxx
.
.
(a-1)xxxx
*/
for(Long i = 1;i <= bit[len] - 1;i++)
{
result += g[len][i];
}
/*
a [0,b)[0,c)[0,d)...
*/
for(Long i = len - 1;i >= 1;i--)
{
for(Long j = 0;j < bit[i];j++)//枚举第i位
{
if(ABS(bit[i + 1] - j) >= 2LL)
result += g[i][j];
}
if(ABS(bit[i] - bit[i + 1]) < 2LL)
break;
}
return result;
}
int main()
{
init();
Long l = 0LL;
Long r = 0LL;
std::cin>>l>>r;
Long result = get_res(r + 1LL) - get_res(l);
//for(int i = 0;i <= 10;i++)
// for(int j = 0;j < 10;j++)
// std::cout<<i<<" "<<g[i][j]<<"\n";
//printf("%d %d\n",i,g[i][j]);
std::cout<<result<<std::endl;
return 0;
}
评论 (0)
