90分wa5求助
查看原帖
90分wa5求助
758211
zhangchenyi0509楼主2024/7/25 15:30
#include <bits/stdc++.h>
using namespace std;
int ta,tb,cnta,cntb,a[14],b[14],dp[14][14][6],ansa,ansb;
bool flag;
int main()
{
	cin>>ta>>tb;
	ta=ta-1;
	while (ta)
	{
		a[++cnta]=ta%10;
		ta=ta/10;
	}
	while (tb)
	{
		b[++cntb]=tb%10;
		tb=tb/10;
	}
	for (int i=1;i<=cnta/2;i++)
	{
		swap (a[i],a[cnta-i+1]);
	}
	for (int i=1;i<=cntb/2;i++)
	{
		swap (b[i],b[cntb-i+1]);
	}
	for (int i=1;i<=cnta&&!flag;i++)
	{
		for (int j=0;j<a[i];j++)
		{
			if (i>1&&abs (j-a[i-1])<=1)
			{
				continue;
			}
			memset (dp,0,sizeof (dp));
			if (i==1&&!j)
			{
				dp[i][j][0]=1;
			}
			else
			{
				dp[i][j][1]=1;
			}
			for (int k=i+1;k<=cnta;k++)
			{
				for (int l=0;l<=9;l++)
				{
					for (int t=0;t<=1;t++)
					{
						if (dp[k-1][l][t])
						{
							for (int x=0;x<=9;x++)
							{
								if (t==1&&abs (x-l)>=2)
								{
									dp[k][x][1]=dp[k][x][1]+dp[k-1][l][t];
								}
								if (!t)
								{
									if (!x)
									{
										dp[k][x][0]=dp[k][x][0]+dp[k-1][0][0];
									}
									else
									{
										dp[k][x][1]=dp[k][x][1]+dp[k-1][0][0];
									}
								}
							}
						}
					}
				}
			}
			for (int k=0;k<=9;k++)
			{
				ansa=ansa+dp[cnta][k][1];
			}
		}
		if (i>1&&abs (a[i]-a[i-1])<=1)
		{
			flag=true;
		}
	}
	flag=false;
	for (int i=1;i<=cntb&&!flag;i++)
	{
		for (int j=0;j<b[i];j++)
		{
			if (i>1&&abs (j-b[i-1])<=1)
			{
				continue;
			}
			memset (dp,0,sizeof (dp));
			if (i==1&&!j)
			{
				dp[i][j][0]=1;
			}
			else
			{
				dp[i][j][1]=1;
			}
			for (int k=i+1;k<=cntb;k++)
			{
				for (int l=0;l<=9;l++)
				{
					for (int t=0;t<=1;t++)
					{
						if (dp[k-1][l][t])
						{
							for (int x=0;x<=9;x++)
							{
								if (t==1&&abs (x-l)>=2)
								{
									dp[k][x][1]=dp[k][x][1]+dp[k-1][l][t];
								}
								if (!t)
								{
									if (!x)
									{
										dp[k][x][0]=dp[k][x][0]+dp[k-1][0][0];
									}
									else
									{
										dp[k][x][1]=dp[k][x][1]+dp[k-1][0][0];
									}
								}
							}
						}
					}
				}
			}
			for (int k=0;k<=9;k++)
			{
				ansb=ansb+dp[cntb][k][1];
			}
		}
		if (i>1&&abs (b[i]-b[i-1])<=1)
		{
			flag=true;
		}
	}
	cout<<ansb-ansa<<endl;
	return 0;
}
2024/7/25 15:30
加载中...