当前位置:网站首页>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
- P4408 [NOI2003] 逃学的小孩(树的直径)
- P4281 [ahoi2008] emergency assembly / gathering (LCA)
- npm install报错 强制安装
- The waterfall flow layout demo2 (method 2) used by the uniapp wechat applet (copy and paste can be used without other processing)
- Binary conversion problem
- Acwing164. Accessibility Statistics (topological sorting +bitset)
- 分布式BASE理论
- 【C】 (written examination questions) pointer and array, pointer
- Distributed base theory
猜你喜欢
What happened to those who focused on automated testing?
npm install报错 强制安装
The waterfall flow layout demo2 (method 2) used by the uniapp wechat applet (copy and paste can be used without other processing)
Hisilicon 3559 universal platform construction: YUV422 pit stepping record
lambda表达式
【Unity】InputSystem
Leetcode70 (Advanced), 322
Continuous modification of business scenario functions
Two numbers replace each other
What you learned in the eleventh week
随机推荐
Detailed explanation of openharmony resource management
[Yocto RM]11 - Features
[Yocto RM]10 - Images
[STM32] (I) overview and GPIO introduction
Apifox (postman + swagger + mock + JMeter), an artifact of full stack development and efficiency improvement
2022.07.03 (LC 6109 number of people who know secrets)
User login function: simple but difficult
uniapp微信小程序拿来即用的瀑布流布局demo2(方法二)(复制粘贴即可使用,无需做其他处理)
There is a new Post-00 exam king in the testing department. I really can't do it in my old age. I have
abc 258 G - Triangle(bitset)
Life is changeable, and the large intestine covers the small intestine. This time, I can really go home to see my daughter-in-law...
GDB常用命令
Identifiers and keywords
Recursive execution mechanism
(script) one click deployment of any version of redis - the way to build a dream
JS how to realize array to tree
Verilog tutorial (11) initial block in Verilog
Several simplified forms of lambda expression
Insert sort of sort
PyTorch: In-place Operation