请问一下为什么dp[12][12]wa了,dp[12][13]能过呢
查看原帖
请问一下为什么dp[12][12]wa了,dp[12][13]能过呢
672837
DaShabby楼主2022/7/20 15:37
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int maxn=1e5+45,MAXN=2e3+5,inf=0x3f3f3f3f;
ll dp[50][12],num[12];
ll dfs(int len,int pre,int limit){
	if(len==0)return 1;
//	if(pre>9) exit(-1);
	if(!limit&&dp[len][pre]!=-1)return dp[len][pre];
	int up=(limit?num[len]:9);ll ans=0;
	for(int i=0;i<=up;i++){
		if(abs(pre-i)>=2){
			int pre_x=i;
			if(pre==-3&&i==0)pre_x=-3;
			ans+=dfs(len-1,pre_x,limit&&i==up);
		}
	}
	if(!limit)dp[len][pre]=ans;
	return ans;
}
ll solve(int x){
	int len=0;
	while(x){
		num[++len]=x%10;
		x/=10;
	}
	return dfs(len,-3,1);
}
int main()
{
	int x,y;
	memset(dp,-1,sizeof(dp));
	scanf("%d%d",&x,&y);
    printf("%lld\n",solve(y)-solve(x-1));
	
	return 0;
}
2022/7/20 15:37
加载中...