数位DP记忆化40pts玄关求调
  • 板块P1836 数页码
  • 楼主baiyh
  • 当前回复2
  • 已保存回复2
  • 发布时间2025/7/24 10:47
  • 上次更新2025/7/24 15:42:44
查看原帖
数位DP记忆化40pts玄关求调
822746
baiyh楼主2025/7/24 10:47

RT

#include<bits/stdc++.h>
#define int long long
using namespace std;
template<typename T>void read(T &x){
	int f=1;x=0;char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
	for(;isdigit(c);c=getchar()) x=(x<<1)+(x<<3)+(c^48);
	x*=f;
} 
const int maxn=2e5+10;
int n;
int dp[20][10];
int num[20],nt[maxn];
int cf(int x,int y){
	if(y==0) return 1;
	return pow(x,y);
}
int dfs(int pos,int pre_num,bool limit){
	if(!pos) return 0;
	if(dp[pos][pre_num]!=-1&&!limit) return dp[pos][pre_num];
	int mx=limit?num[pos]:9;
	int res=0;
	for(int i=0;i<=mx;i++){
		if(limit&&i==num[pos]) res+=(i*nt[pos]+i+dfs(pos-1,i,limit&&(i==num[pos])));
		else res+=(i*cf(10,pos-1)+dfs(pos-1,i,limit&&(i==num[pos])));
	}
	if(!limit) dp[pos][pre_num]=res;	
	return res;
}
int solve(int x){
	memset(dp,-1,sizeof(dp));
	int cnt=0;
	int k=x;
	while(x){
		num[++cnt]=x%10;
		x/=10;
	} 
	for(int i=1;i<cnt;i++){
		nt[i+1]=num[i]*cf(10,i-1)+nt[i];
	}
	return dfs(cnt,0,1);
}
signed main(){
	read(n);
	printf("%d",solve(n));
	return 0;
}
2025/7/24 10:47
加载中...