当前位置:网站首页>Digital DP template
Digital DP template
2022-07-05 00:50:00 【Krito.】
Simply save a board , In order to avoid going through documents and websites everywhere in the future .
notes : Not to explain , For personal use only .
explain
choose P2602 [ZJOI2010] The problem of number counting AC Code as a template .
1.dp Of n Each dimension of the dimension group represents a certain current state , Take this question as an example ,dp[pos][sum][st] in ,pos Represents the current number ,sum Indicates the number of occurrences of a number in the higher-order digits of the current digit ,st Indicates whether there is a leading 0.
2.dfs Search the possible value of each digit and save the current state . Again , Take this question as an example ,pos Indicates the current digit ,pre Indicates the size of the previous digit ( This question seems useless ),st Indicates whether it is a leading 0,sum Indicates the number of occurrences of a certain number so far ,limit Indicates whether there is a size limit for the current digit .
3.solve What you get is [0,x] The number of intervals that meet the requirements , Want to get [L,R], use solve(R)-solve(L-1) that will do .
4. Make a reasonable plan dp Number and meaning of dimensions of array ,dfs The state of being carried , The filter condition is digits dp The key to .
Templates
/*@_krito*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define LM LLONG_MAX
#define IM INT_MAX
#define _for(i,a,b) for(int i=a;i<=b;i++)
ll dp[15][15][2];
int a[15];
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
int spot;
ll dfs(int pos,int pre,int st,int sum,int limit){
if(!pos) return sum;
if(!limit&&dp[pos][sum][st]!=-1) return dp[pos][sum][st];
ll res=0;
int maxn=limit?a[pos]:9;
_for(i,0,maxn){
res+=dfs(pos-1,i,st&&(i==0),sum+((!st||i)&&(i==spot)),limit&&i==maxn);
}
dp[pos][sum][st]=res;
return res;
}
ll solve(ll x)
{
ll ans;
int len=0;
while(x) a[++len]=x%10,x/=10;
memset(dp,-1,sizeof(dp));
return ans=dfs(len,0,1,0,1);
}
int main(){
ll ANS=0;
ll L,R;
scanf("%lld%lld",&L,&R);
_for(i,0,9){
spot=i;
printf("%lld ",solve(R)-solve(L-1));
}
}
边栏推荐
- [Yocto RM]11 - Features
- Arbitrum:二维费用
- User login function: simple but difficult
- [circuit design] optocoupler use and circuit design summary
- Identifiers and keywords
- lambda expressions
- [selenium automation] common notes
- dotnet-exec 0.6.0 released
- What you learned in the eleventh week
- 华为百万聘请数据治理专家!背后的千亿市场值得关注
猜你喜欢
海思3559万能平台搭建:YUV422的踩坑记录
npm install报错 强制安装
NPM install error forced installation
Les phénomènes de « salaire inversé » et de « remplacement des diplômés » indiquent que l'industrie des tests a...
揭露测试外包公司,关于外包,你或许听到过这样的声音
Arbitrum:二维费用
SAP UI5 应用开发教程之一百零六 - 如何提高 SAP UI5 应用路由 url 的可读性试读版
Oracle case: SMON rollback exception causes instance crash
The waterfall flow layout demo2 (method 2) used by the uniapp wechat applet (copy and paste can be used without other processing)
Relationship between classes and objects
随机推荐
GDB common commands
7. Scala process control
abc 258 G - Triangle(bitset)
Insert sort of sort
Get to know ROS for the first time
Enterprise application business scenarios, function addition and modification of C source code
GDB常用命令
华为百万聘请数据治理专家!背后的千亿市场值得关注
Hisilicon 3559 universal platform construction: YUV422 pit stepping record
各大主流编程语言性能PK,结果出乎意料
ORB(Oriented FAST and Rotated BRIEF)
Parameter passing mechanism of member methods
Detailed explanation of multi-mode input event distribution mechanism
"Upside down salary", "equal replacement of graduates" these phenomena show that the testing industry has
Kibana index, mapping, document operation
AcWing164. 可达性统计(拓扑排序+bitset)
Inventory of more than 17 typical security incidents in January 2022
Visual explanation of Newton iteration method
1189. Maximum number of "balloons"
Reasons and solutions of redis cache penetration and avalanche