萌新刚学OI,求调简单dp
查看原帖
萌新刚学OI,求调简单dp
1037152
cyyyyds857857楼主2023/8/22 22:02

已经A了,尝试用另一种方法做,可是却只有11pts~~(帮大号问的,大号被jc禁言了(~~

另外,这题评紫是不是有点太水了,建议评蓝~~(虽然这种方法没有A ~~

#include<bits/stdc++.h>
using namespace std;
#define int long long
int l,r,p,sum[105];
int dp[105][105][105];
int dfs(int pos,int pre1,int pre2,bool lead,bool lim){
	if(!pos){
		return 1;
	}
	if(!lim&&!lead&&dp[pos][pre1+1][pre2+1]!=-1){
		return dp[pos][pre1+1][pre2+1];
	}
	int up,ans=0;
	if(lim){
		up=sum[pos];
	}else{
		up=9;
	}
	for(int i=0;i<=up;i++){
		if(i!=pre1&&i!=pre2){
			ans+=dfs(pos-1,(!lead||i)?i:-1,pre1,lead&&i!=0,lim&&i==up);
		}
	}
	if(!lim&&!lead){
		dp[pos][pre1+1][pre2+1]=ans;
	}
	return ans;
}
int solve(int x){
	int cnt=0;
	while(x){
		sum[++cnt]=x%10;
		x/=10;
	}
	memset(dp,-1,sizeof dp);
	return dfs(cnt,-1,-1,1,1);
}
signed main(){
	cin>>l>>r;
	cout<<solve(r)-solve(l-1)<<"\n";
	return 0;
}
2023/8/22 22:02
加载中...