算法学习————

记忆化搜索版，比较有套路

就根据杠杆数这道题来回忆一下

题目大致意思：选定大数中的某个数作为支点，使左右两边的力矩和相等，求区间内能满足条件的数的个数

首先一个大前提：对于一个满足条件的数来说，他的支点确定

如何证明：以将支点向左移动为例，支点左侧的力矩和因为支点向左移动，导致整体的力矩减少，并且数字个数减少一个，其他数字不变，所以可证，左边的力矩和减小，右边的力矩和增大，找不出第二个支点位置，可以使两边的力矩和相等

整体做法：枚举支点的位置，进行dp

一些细节：

我们不用分清左右，当位置在左时pos-x为负，当位置在右时，pos-x为正，这样我们只要保证最后的力矩和为0就ok了
当力矩和 < 0时不用继续向下搜索，因为我们是从右往左挨个位置依次搜索，所以左边为正的力矩已经全部计算完毕，当为负时，只会越减越少
一些数位dp的套路（是否有前导0，是否有数字的最大限制），最开始的初始化为1
因为每次枚举支点会把0000000……给计算上，所以最后的答案为ans-cnt+1

其实我在很多算法上，了解的都不是很深刻，有的算法甚至只是会做某一道题目，自己的道路还很漫长

代码：

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <iostream>

#define B cout<<"Breakpoint"<<endl;

#define O(x) cout<<#x<<" "<<x<<endl;

#define int long long

using namespace std;

int read(){

	int x = 1,a = 0;char ch = getchar();

	while (ch < '0'||ch > '9'){if (ch == '-') x = -1;ch = getchar();}

	while (ch >= '0'&&ch <= '9'){a = a*10+ch-'0';ch = getchar();}

	return x*a;

}

int a,b;

int dp[20][20][2005],num[2005];

int dfs(int pos,int x,bool flag,bool lim,int sum){

	if (!pos) return sum == 0;

	if (sum < 0) return 0;

	if (!lim&&dp[pos][x][sum] != -1) return dp[pos][x][sum];

	int maxx = lim ? num[pos] : 9,ans = 0;

	for (int i = 0;i <= maxx;i++){

		if (flag) ans += dfs(pos-1,x,i == 0,lim&&i == maxx,sum+i*(pos-x));

		else ans += dfs(pos-1,x,0,lim&&i == maxx,sum+i*(pos-x));

	}

	if (!flag&&!lim) return dp[pos][x][sum] = ans;

	return ans;

}

int solve(int x){

	int ans = 0,cnt = 0;

	while (x){

		num[++cnt] = x % 10;

		x /= 10;

	}

	for (int i = 1;i <= cnt;i++) ans += dfs(cnt,i,1,1,0);

	return ans-cnt+1;

}

signed main(){

	memset(dp,-1,sizeof(dp));

	a = read(),b = read();

	if (!a) cout<<solve(b)<<endl;

	else cout<<solve(b) - solve(a-1)<<endl;

	return 0;

}

巴特西

算法学习—————数位dp

最新文章

热门文章