2657 windy数

本文主要是介绍2657 windy数，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

2657 windy数

啊，连了一天的动态规划，快给我整吐了，不过状压DP还没学，效率太低了，明天再用一天学完DP加上图论数据结构，然后拿出两整天的时间来学数论，如果济南夏令营还去的话，回来就备考初赛
数位dp的题，一般会给你l和r，求从l到r有多少个数满足某个性质
我们用f(i)表示前i位windy数的个数
那么答案就是f(r+1)-f(l)有点类似于区间DP
设f[i][j]表示位数位i最高位是j的windy数个数
方程：
f[i][j]=f[i-1][k]其中k是非负整数，k是0，9之间的数
边界f[1][i]=1其中i是非负整数，i是0，9之间的数
怎么求f(x)?
为了方便先对x进行10进制拆分，这个操作很经典
1.显然位数比x小的数字都在1，x区间直接统计
2.位数和x一样最高位数字比x小的数字都在1，x区间直接统计
3.位数和x一样最高位和x一样，从左往右扫一遍x各个位，然后判断合法就好了

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
using namespace std;
typedef long long ll;
const int SIZE=20;
ll f[SIZE][SIZE]; 
ll a[SIZE]; 
ll n,m;
ll sol(ll x)
{
	int len=0;
	while(x>0ll) a[++len]=x%10,x/=10;
	ll sum=0ll;//0ll相当于0，长整型下的0 
	for(int i=1;i<=len-1;i++)
		for(int j=1;j<=9;j++)//枚举每一位数
			sum+=f[i][j];//计算所有可能的数 
	for(int i=1;i<a[len];i++) sum+=f[len][i];
	
	for(int i=len-1;i>=1;i--)
	{
		for(int j=0;j<=a[i]-1;j++)
			if(abs(j-a[i+1])>=2) sum+=f[i][j];
		if(abs(a[i+1]-a[i])<2) break;//小优化 
	}
	return sum;
}
int main()
{
	cin>>n>>m;
	if(n>m) swap(n,m);
	for(int i=0;i<=9;i++)
		f[1][i]=1ll;//初始化1 
	for(int i=2;i<=10;i++)
	{
		for(int j=0;j<=9;j++)
		{
			for(int k=0;k<=9;k++)
			{
				if(abs(k-j)>=2) f[i][j]+=f[i-1][k];//计算f 
			}
		}
	 } 
	 cout<<sol(m+1)-sol(n)<<endl; 
	 return 0;
}

这篇关于2657 windy数的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！