当前位置:网站首页>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));
}
}
边栏推荐
- pycharm专业版下载安装教程
- Implementation steps of master detail detail layout mode of SAP ui5 application
- 【C】 (written examination questions) pointer and array, pointer
- 【报错】 “TypeError: Cannot read properties of undefined (reading ‘split‘)“
- AcWing164. 可达性统计(拓扑排序+bitset)
- GDB common commands
- uniapp微信小程序拿来即用的瀑布流布局demo2(方法二)(复制粘贴即可使用,无需做其他处理)
- 初识ROS
- 大专学历,33岁宝妈又怎样?我照样销售转测试,月入13k+
- The most complete regular practical guide of the whole network. You're welcome to take it away
猜你喜欢
SAP UI5 应用的主-从-从(Master-Detail-Detail)布局模式的实现步骤
Les phénomènes de « salaire inversé » et de « remplacement des diplômés » indiquent que l'industrie des tests a...
Huawei employs millions of data governance experts! The 100 billion market behind it deserves attention
dotnet-exec 0.6.0 released
P3304 [SDOI2013]直径(树的直径)
各大主流编程语言性能PK,结果出乎意料
Hisilicon 3559 universal platform construction: YUV422 pit stepping record
Parsing of XML
What if the programmer's SQL data script coding ability is weak and Bi can't do it?
两个数相互替换
随机推荐
Maximum number of "balloons"
[Yocto RM]11 - Features
两个数相互替换
Enterprise application business scenarios, function addition and modification of C source code
uniapp微信小程序拿来即用的瀑布流布局demo2(方法二)(复制粘贴即可使用,无需做其他处理)
||Interview questions you will encounter
初识ROS
P3304 [sdoi2013] diameter (diameter of tree)
The waterfall flow layout demo2 (method 2) used by the uniapp wechat applet (copy and paste can be used without other processing)
107. SAP UI5 OverflowToolbar 容器控件以及 resize 事件处理的一些细节介绍
Playwright recording
P4281 [ahoi2008] emergency assembly / gathering (LCA)
Date time type and format in MySQL
The difference between string STR and new string
pycharm专业版下载安装教程
Huawei employs millions of data governance experts! The 100 billion market behind it deserves attention
Get to know ROS for the first time
There is a new Post-00 exam king in the testing department. I really can't do it in my old age. I have
【Unity】InputSystem
[STM32] (I) overview and GPIO introduction