您好,欢迎访问代理记账网站
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

洛谷:P1831 杠杆数(数位dp)

文章目录

  • 描述
  • 解析
  • 代码
  • thanks for reading!

传送门

描述

如果把一个数的某一位当成支点,且左边的数字到这个点的力矩和等于右边的数字到这个点的力矩和,那么这个数就可以被叫成杠杆数。

比如4139就是杠杆数,把3当成支点,我们有这样的等式:4 * 2 + 1 * 1 = 9 * 1。

给定区间[x,y],求出在[x,y]中有几个杠杆数。

解析

数位dp
具体实现看代码注释吧

代码

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
int n;
#define int long long
ll dp[20][20][5000];
ll num[20],cnt;
/*
dp定义
dp[pos][pl][num1]
位数为pos,杠杆支点位置在pl,力矩和为num1的数字的个数
*/
ll find(int pos,int pl,int num1,bool lim,bool flag){
//flag:判断前导〇
//lim判断是否受最高位限制
	if(num1<0) return 0;//如果杠杆力矩已经是负的了,以后只会更负,所以回去
	if(pos==0) return num1==0;//填完如果力矩还需要0就符合条件
	if(!lim&&dp[pos][pl][num1]!=-1) return dp[pos][pl][num1];//记忆化
	int mx= lim ? num[pos] : 9;//可以填的最高位数
	ll ans=0;
	for(int i=0;i<=mx;i++){
		ans+=find(pos-1,pl,num1+(pos-pl)*i,lim&&i==mx,flag&&i==0);//枚举当前需要填的位数
	}
	if(!lim) dp[pos][pl][num1]=ans;//记忆化
	return ans;
}
ll solve(int x){
	cnt=0;
	while(x){
		num[++cnt]=x%10;x/=10;//把每一位存起来
	}
	ll ans=0;
	for(int i=1;i<=cnt;i++) ans+=find(cnt,i,0,1,1);//枚举杠杆支点位置
	return ans-cnt+1;
}
signed main(){
		ll l,r;
		memset(dp,-1,sizeof(dp));
		scanf("%lld%lld",&l,&r);
		if(l==0) printf("%lld\n",solve(r));
		else printf("%lld\n",solve(r)-solve(l-1));//用前缀和相减
}
/*
if(flag) ans+=find(pos-1,pl,(pos-pl)*i,lim&&i==mx,flag&&i==0);
		else ans+=find(pos-1,pl,num1+(pos-pl)*i,lim&&i==mx,flag&&i==0);
*/

thanks for reading!


分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进