如下代码:数组定义部分,len在最前面定义是100分,在最后定义是30分(评测记录)
非常不解,这两种写法有什么区别?
#include<bits/stdc++.h>
using namespace std;
#define int long long
int dp[10][10];
int a[10];
int len;//30分写法
//int len;
//int dp[10][10];
//int a[10];//AC写法
int dfs(int n,int lst,int zero,bool fmax)
{
if(!n) return 1;
if(!fmax&&!zero&&dp[n][lst]!=-1) return dp[n][lst];
int ans=0;
int m=fmax?a[n]:9;
for(int i=0;i<=m;i++)
if(abs(i-lst)>=2||zero)
ans+=dfs(n-1,i,zero&&i==0,fmax&&i==m);
if(!fmax&&!zero) dp[n][lst]=ans;
return ans;
}
int solve(int n)
{
for(len=0;n>0;n/=10)
a[++len]=n%10;
return dfs(len,0,1,1);
}
signed main()
{
int n,m;
cin>>n>>m;
memset(dp,-1,sizeof(dp));
long long ans=solve(m)-solve(n-1);
printf("%lld",ans);
return 0;
}