fzu 2109 Mountain Number 数位DP 递推

#include<iostream>#include<cstdio>using namespace std;int dp[12][10]={0},pd[12][10]={0},ans[12]={0};int solve(int n){	int a[12]={0},cnt=0,ans1=0,flag=1,t=1;	while(n)	{		cnt++;		a[cnt]=n%10;		n /=10;	}	ans1 +=ans[cnt];	a[cnt+1]=9;  while(cnt)  {  	  	if(flag) 	     {	     for(int i=0;i<=9;i++) 	     {	       if(t&&!i) 		 {		 	t=0;		 	continue;		 }		 if(i<=a[cnt+1]&&i<a[cnt]) 		 ans1 +=dp[cnt][i];		}flag=0;	}  	else {for(int i=0;i<=9;i++) if(i>=a[cnt+1]&&i<a[cnt]) ans1 +=pd[cnt][i];flag=1;}  	if(!flag) if(a[cnt]>a[cnt+1]) break;  	if(flag) if(a[cnt]<a[cnt+1]) break;  	cnt--;  	if(cnt==0) ans1++;  }  return ans1;}int main(){	for(int i=0;i<=9;i++) 	{ 	  dp[1][i]=1;	  pd[1][i]=1;    }    for(int i=2;i<=11;i++)     {     	ans[i]=ans[i-1];     	for(int j=0;j<=9;j++)     	{     		for(int k=0;k<=9;k++)     		{     			if(j>=k) pd[i][j] +=dp[i-1][k];				if(j<=k) dp[i][j] +=pd[i-1][k]; 			}			if(j) ans[i] +=dp[i-1][j];		}	 }	int t,l,r;	scanf("%d",&t);	while(t--)	{		scanf("%d%d",&l,&r);		int ansans=solve(r)-solve(l-1);		PRintf("%d/n",ansans);	}	return 0;}