hdu6148

思路

一个数位dp模板题，注意判断前导0。用一个bz来记录当前是应该增还是可增可减。然后排除不满足条件的情况并进行dp即可。

代码

#include<cstdio>

#include<iostream>

#include<cstring>

using namespace std;

typedef long long ll;

const int mod=1000000007;

ll read() {

	ll x=0,f=1;char c=getchar();

	while(c<'0'||c>'9') {

		if(c=='-') f=-1;

		c=getchar();

	}

	while(c>='0'&&c<='9') {

		x=x*10+c-'0';

		c=getchar();

	}

	return x*f;

}

char c[110];

int a[110],n;

ll f[110][20][5];

ll dfs(int pos,int lst,int limit,int fx,int Rea) {//fx为0表示可增可减，fx为1表示只能增

	if(pos==n+1) return Rea;

	if(f[pos][lst][fx]!=-1&&!limit&&Rea) return f[pos][lst][fx];

	int up=limit?a[pos]:9;

	ll ans=0;

	for(int i=up;i>=0;--i) {

		if(fx==1&&i<lst) break;

		int p=fx;

		if(i>lst) p=1;

		if(!Rea) p=0;

		ans+=dfs(pos+1,i,limit&&i==up,p,Rea||i);

		ans%=mod;

	}

	if(!limit) f[pos][lst][fx]=ans;

	return ans;

}

int main() {

	int T=read();

	while(T--) {

		scanf("%s",c+1);

		n=strlen(c+1);

		for(int i=1;i<=n;++i)

			a[i]=c[i]-'0';

		memset(f,-1,sizeof(f));

		printf("%lld\n",dfs(1,10,1,0,0));

	}

	return 0;

}

巴特西

[hdu6148][Valley Numer]

hdu6148

思路

一个数位dp模板题，注意判断前导0。用一个bz来记录当前是应该增还是可增可减。然后排除不满足条件的情况并进行dp即可。

代码

最新文章

热门文章