【百度之星复赛】T5 Valley Numer

Valley Numer

Problem Description

众所周知，度度熊非常喜欢数字。

它最近发明了一种新的数字：Valley Number，像山谷一样的数字。

当一个数字，从左到右依次看过去数字没有出现先递增接着递减的“山峰”现象，就被称作 Valley Number。它可以递增，也可以递减，还可以先递减再递增。在递增或递减的过程中可以出现相等的情况。

比如，1，10，12，212，32122都是 Valley Number。

121，12331，21212则不是。

度度熊想知道不大于N的Valley Number数有多少。

注意，前导0是不合法的。

Input

第一行为T，表示输入数据组数。

每组数据包含一个数N。

● 1≤T≤200

● 1≤length(N)≤100

Output

对每组数据输出不大于N的Valley Number个数，结果对 1 000 000 007 取模。

Sample Input

3
3
14
120

Sample Output

3
14
119

题解：裸的数位DP。用f[i][j][0/1/2]表示i位，最高位为j，当前处于 递减/递增/平 状态的数的个数。然后尽情讨论吧！

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
typedef long long ll;
const ll mod=1000000007;
ll f[110][12][3];
//0 减 1 增 2 未知
int v[110];
char str[110];
ll ans;
int n,tag,tmp;
void init()
{
	int i,j,k;
	for(i=0;i<=9;i++)	f[1][i][2]=1;
	for(i=2;i<=100;i++)
	{
		for(j=0;j<=9;j++)
		{
			f[i][j][2]=f[i-1][j][2];
			for(k=0;k<=9;k++)
			{
				if(j<=k)	f[i][j][1]=(f[i][j][1]+f[i-1][k][1])%mod;
				if(j<k)	f[i][j][1]=(f[i][j][1]+f[i-1][k][2])%mod;
				if(j>=k)	f[i][j][0]=(f[i][j][0]+f[i-1][k][0])%mod;
				if(j>k)	f[i][j][0]=(f[i][j][0]+f[i-1][k][1]+f[i-1][k][2])%mod;
			}
		}
	}
}
void work()
{
	scanf("%s",str),n=strlen(str);
	int i,j;
	ans=0,tag=2;
	for(i=1;i<=n;i++)	v[i]=str[n-i]-'0';
	for(i=1;i<n;i++)	for(j=1;j<=9;j++)	ans=(ans+f[i][j][0]+f[i][j][1]+f[i][j][2])%mod;
	for(i=n;i>=1;i--)
	{
		for(j=(i==n)?1:0;j<v[i];j++)
		{
			tmp=tag;
			if(i!=n&&j>v[i+1])	tmp=1;
			if(i!=n&&j<v[i+1])
			{
				if(tag==1)	continue;
				tmp=0;
			}
			if(tmp==2)
			{
				ans=(ans+f[i][j][0]+f[i][j][1]+f[i][j][2])%mod;
			}
			if(tmp==1)
			{
				if(j>=v[i+1])	ans=(ans+f[i][j][1]+f[i][j][2])%mod;
			}
			if(tmp==0)
			{
				if(j<=v[i+1])	ans=(ans+f[i][j][0]+f[i][j][1]+f[i][j][2])%mod;
				if(j>v[i+1])	ans=(ans+f[i][j][1]+f[i][j][2])%mod;
			}
		}
		if(i!=n&&v[i]>v[i+1])	tag=1;
		if(i!=n&&v[i]<v[i+1])
		{
			if(tag==1)	break;
			tag=0;
		}
	}
	if(!i)	ans=(ans+1)%mod;
	printf("%lld
",ans);
}
int main()
{
	int T;
	init();
	scanf("%d",&T);
	while(T--)	work();
	return 0;
}//1 130