本文主要是介绍蓝桥第 6 场 强者挑战赛 谁是帕鲁|数位DP模板，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接
0谁是帕鲁？【算法赛】 - 蓝桥云课 (lanqiao.cn)
说明：
练习一下数位DP的模板。模板（还有2.0版本，但这里1.0够用了）来自：
2376. 统计特殊整数 - 力扣（LeetCode）
小结：
1.dfs参数一般至少有三个，第一个i标识填了多少个位置，limit是标识前面的位数是否填的对应位，来控制当前位填的上限，isnum是标识前面有没有填 非0数（标记前导零），用来控制下限（0还是1开始），对于上面的两道题还需要一个参数来区分状态，也就是dp数组的第二维，帕鲁这道题的第二维是前面填的数已经有多少个封闭图形了，这样区分之后，返回的记录才是对的。比如：1x和4x这两个对应的dp是不一样的，一个 个位之前的封闭图形数 是0，一个是1，若需要求k==2的数，前者对应的数量是1（18），后者是4（40，44，46，49）。
2.这个模板是计算的1到n的，如果要求给定区间[l，r]，需要求两次，r和l-1，用前缀和思想相减得区间的值。
3.第一次调用该函数时，传进的limit是true，因为第一个位置是有大小限制的，不能任意选。
4.C++的整数转string函数：to_string(n)
5.limit为真或isnum为false的情况不用记录，因为这种情况只会出现一次，不会重复出现，其他情况会重复出现，才记忆化。
代码：
//#include<iostream>
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=1e3+10;int n,ans1=0,ans2;
int l,r,k;
int len=0;string s;int dp[13][25];
int closen[11]={1,0,0,0,1,0,1,0,2,1};int f(int i, bool limit, bool isnum,int cnt) {//所有数位都填完if (i == len) {if(cnt==k)//这里不能直接输出1return (isnum?1:0);elsereturn 0;}if (dp[i][cnt] != -1 && !limit && isnum) return dp[i][cnt];int res = 0;//前面的数都跳过，这位数可以选择跳过//if(!isnum) res+=f(i+1,mask,limit,isnum);应该limit为false，// 第一次传进来的limit是true，因为第一个数限制在0-s[0]if (!isnum) res += f(i + 1, false, false,0);//选择不跳过，枚举数，根据情况可以填0-9，还是1-9还是0-s[i]//上限值int up=limit?s[i]-'0':9;for (int low = (isnum == true ? 0 : 1); low <= up; low++) {if(cnt+closen[low]<=k)res += f(i + 1, limit && (low == up), true,cnt+closen[low]);}if (!limit&&isnum) dp[i][cnt] = res;return res;} int palu(int n) {s = std::to_string(n);len = s.size();memset(dp, -1, sizeof(dp));int ans=f(0, true, false,0);return ans;}signed main() {cout.tie(0);cin.tie(0);cin>>l>>r>>k;if(l==1) ans1=0;elseans1=palu(l-1);if(r==1) ans2=0;else ans2=palu(r);cout<<ans2-ans1;return 0;
}
这篇关于蓝桥第 6 场 强者挑战赛 谁是帕鲁|数位DP模板的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
