20230719-动态规划DP

H_W_Y / 2023-07-20 / 原文

20230719

线性DP

P1020 [NOIP1999 普及组] 导弹拦截

题目描述

传送门
给定一个长度为\(N\)的序列\(a\)，求最少能划分成多少个不上升序列
\(1 \le N \le 10^5\)

Solution

一个小结论：
最小不上升子序列个数=最大上升子序列

很容易证明
每一个最大上升子序列中的数都是一个不上升子序列的开头

那这道题就是求最长上升子序列
我直接维护了一个树状数组……

H_W_Y-Coding

#include <bits/stdc++.h>
using namespace std;

const int maxn=1e5+10;
int ans,res,len=0,n,f[maxn],x,t[maxn],b[maxn],a[maxn];

int lowbit(int i){return i&(-i);}
void update(int x,int val){for(int i=x;i<=n;i+=lowbit(i)) t[i]=max(t[i],val);}
int query(int x){
  int res=0;
  for(int i=x;i>0;i-=lowbit(i)) res=max(res,t[i]);
  return res;
}

int main(){
  /*2023.7.20 H_W_Y P1020 [NOIP1999 普及组] 导弹拦截 DP*/
  while(scanf("%d",&x)!=EOF) a[++n]=x,b[n]=a[n];
  sort(b+1,b+n+1);
  len=unique(b+1,b+n+1)-b-1;
  for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+len+1,a[i])-b;
  for(int i=1;i<=n;i++){
  	f[i]=query(a[i]-1)+1;
  	ans=max(f[i],ans);
  	update(a[i],f[i]);
  	a[i]=n-a[i]+1;
  }
  memset(t,0,sizeof(t));
  for(int i=1;i<=n;i++){
  	f[i]=query(a[i])+1;
  	res=max(res,f[i]);
  	update(a[i],f[i]);
  }
  printf("%d\n%d\n",res,ans);
  return 0;
}

数位DP

P4127 [AHOI2009] 同类分布

题目描述

传送门
求出 [a,b] 中各位数字之和能整除原数的数的个数 \(a,b ≤ 1e18\)

Solution

对于这种求是否能整除的题
我们只有在最后才能得到答案

这道题很明显是数位DP
考虑用记忆化搜索来实现
对于每一位我们需要维护前面的数字之和和前面所组成的数
而由于前面所组成的数太大了，可以到达\(1e18\)
但是数字之和又一定\(\le 9* 18\)

我们就考虑取模数
这样进行\(9 * 18\)次dfs即可
每一次要判断数字之和\(=mod\)
这样记录答案就可以了

H_W_Y-Coding

#include <bits/stdc++.h>
using namespace std;
#define ll long long

ll a,b,mod,dp[20][185][185];
int len=0,p[20];

ll dfs(int id,int sum,ll st,int limit){
  if(id>len) return st==0&&sum==mod?1:0;
  if(!limit&&dp[id][sum][st]!=-1) return dp[id][sum][st];
  int u=limit?p[id]:9;
  ll res=0;
  for(int i=0;i<=u;i++)
    res+=dfs(id+1,sum+i,(st*10+i)%mod,limit&&i==u);
  if(!limit) dp[id][sum][st]=res;
  return res;
}

ll solve(ll x){
  len=0;
  while(x){
  	p[++len]=x%10;
  	x/=10;
  }
  ll res=0;
  for(int i=1;i<=len/2;i++) swap(p[i],p[len-i+1]);
  for(mod=1;mod<=9*len;mod++){
    memset(dp,-1,sizeof(dp));
    res+=dfs(1,0,0,1);
  }
  return res;
}

int main(){
  /*2023.7.19 H_W_Y P4127 [AHOI2009] 同类分布 数位DP*/ 
  scanf("%lld%lld",&a,&b);
  printf("%lld\n",solve(b)-solve(a-1));
  return 0;
}