状态设计及转移方程请移步zhx DP第四讲
这里只对前导零的处理做简要讨论
考虑前导零会对哪些状态的转移产生影响,发现： f[i][p][j]由f[i+1][p][k]转移而来时，如果第i+1位至最高位全为0且j不为零，则f[i][p][j]应为1。 我们可以在初始化时把所有填零的情况的f值赋为1，这样000j___便会正常转移；因为f统计的是个数，而___0一定包含0000的情况，此情况可以看做单独的0，是windy数，所以这样不会重复统计。由于转移时判断相邻两位之差大于等于2，故0001___仍然无法正常转移。仿照上文思路，可将所有填1的情况的f值赋为1，但此时第二维不一定全为0，如果原数最高位为1则第二维为1。以上是初始化二。
#include<bits/stdc++.h>
using namespace std;
int a,b,num[15];//num存数的每一位
long long f[15][2][10];//注意开隆隆
long long dp(int x)//dp(x)计算[0,x]区间内windy数的个数
{
memset(f,0,sizeof(f));
memset(num,0,sizeof(num));//注意清零
int len=0;//len储存数x的长度
long long ans=0;//ans记录答案
if(x==0) return 1;//特判0的情况
for(;x;x/=10) num[++len]=x%10;//将x存到num数组中
//初始化一
for(int i=0;i<=num[len];i++)
f[len][i==num[len]][i]=1;
//初始化二
for(int i=1;i<=len;i++)
f[i][0][0]=f[i][i==len&&num[len]==1][1]=1;
//DP
for(int i=len;i>0;i--)
for(int p=0;p<=1;p++)
for(int k=0;k<=9;k++)
for(int j=0;j<=9;j++)
{
if(p&&j>num[i]) continue;
if(abs(j-k)>1) f[i][p&&(j==num[i])][j]+=f[i+1][p][k];
}
//求和
for(int i=0;i<=9;i++)
ans+=f[1][0][i]+f[1][1][i];
return ans;
}
int main()
{
cin>>a>>b;
cout<<dp(b)-dp(a-1);//注意a-1
return 0;
}
共 1 条回复
%%%