dp

数位dp

模板

//下标从1开始统计 初始化均1开始
ll dfs(int pos,int pre_num,int c,int flag) {
	int max_number;
	if(pos<=0) return c==0;
	if(!flag&&dp[pos][pre_num][c]!=-1) return dp[pos][pre_num][c];
	if(flag) max_number=upper[pos];
	else max_number=9;
	ll ret=0;
	for(int i=0; i<=max_number; i++) {
	//转移方程
		ret+=dfs(pos-1,(i+pre_num)%m,((c-i*p[pos]+pre_num*i)%m+m)%m,flag&&(i==max_number));
		ret=(ret+mod)%mod;
	}
	ret=(ret+mod)%mod;
	if(!flag) dp[pos][pre_num][c]=ret;
	return ret;
}
//以下为处理两个数的减操作
for(int i=len-1; i>=0; i--) {
		if(a[i]>='0'&&a[i]<='9') break;
		a[i]='9',a[i-1]--;
	}
//以下为计算
	}
	for(int i=0; i<len; i++) {
		upper[len-i]=a[i]-'0';
	}
	ll aa=dfs(len,0,0,1);

队列优化

例题引入： 1087. 修剪草坪 - AcWing题库

dp值为枚举每个点作为最右端点，往前算的时候也是算到枚举值的右边

设选择了j个

dp[i]=max({pre[i]-pre[i-j]+f[i-j-1]}) 表示第j个不算 往前找j个的最大值

在不优化的情况下，这个是n*m的复杂度

单调队列处理pre[i-j]+f[i-j-1],可以把复杂度优化到O(n);

int a[MAXN];
int dp[MAXN];//以i为右端点的前缀数组最大值
deque<int> que;//维护dp[i-1]-a[i]的值 
int g(int x){
	return dp[x-1]-a[x];
}
void solve(){
	int n,m;cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++) a[i]=a[i]+a[i-1];
	que.push_back(0);
	for(int i=1;i<=n;i++){
		while(que.size()&&i-que.front()>m) que.pop_front();//丢掉不符合条件的 
		while(que.size()&&g(i)>=g(que.back())) que.pop_back();//替代条件差的 
		que.push_back(i);
		dp[i]=a[i]+g(que.front());
	}
	cout<<dp[n];
}