数位dp+状态压缩dp+数据结构优化的dp

数位DP

P4124 CQOI2016 手机号码

P4124 CQOI2016 手机号码

从后向前每一位进行遍历，注意判断的结束，题目约束。这里用记忆化，代码短，跑得快。

代码

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<stack>
using namespace std;
long long r_r(){//快读 
  long long x=0,f=1;
  char c=getchar();
  while(!isdigit(c)){
    if(c=='-')f=-1;
    c=getchar();
  }
  while(isdigit(c)){
    x=(x<<1)+(x<<3)+(c^48);
    c=getchar();
  }
  return x*f;
}
long long l,r,d_p[15][11][11][2][2][2];
int s_t[15];
//k 当前位置，a 上位数，b 上上位数，b_b 是否出现三个连续数字，n_8 是否出现 8，n_4 是否出现 4，l_t 当前位置的数是否达到上限 
long long d_f(int k,int a,int b,bool b_b,bool n_8,bool n_4,bool l_t){
  if(n_8&&n_4)return 0;//8 和 4 不能同时出现 
  if(!k)return b_b;
  if(!l_t&&d_p[k][a][b][b_b][n_8][n_4]!=-1)//不是最后一位并且比遍历过 
    return d_p[k][a][b][b_b][n_8][n_4];//直接返回记忆存的值 
  long long a_s=0;//初始化统计答案 
  int m_x=l_t?s_t[k]:9;//如果不最后一位，返回 9，否则返回原字符串中当前位置的值 
  for(int i=0;i<=m_x;i++)//范围内的数字都可取 
    a_s+=d_f(k-1,i,a,b_b||(i==a&&i==b),n_8||(i==8),n_4||(i==4),l_t&&(i==m_x));//向前为遍历，统计 
  if(!l_t)d_p[k][a][b][b_b][n_8][n_4]=a_s;//不是最后一位，更新 
  return a_s;//返回统计值 
}
long long f_i(long long x){
  int l_n=0;
  while(x){//差分数 
    s_t[++l_n]=x%10;
    x/=10;
  }
  if(l_n!=11)return 0;//说明号码 11 为不是 11 位，直接返回 
  memset(d_p,-1,sizeof(d_p));//赋初值 
  long long a_s=0;//初始化 
  for(int i=1;i<=s_t[l_n];i++)//枚举最后一位 
    a_s+=(long long)d_f(l_n-1,i,0,0,i==8,i==4,i==s_t[l_n]);
  return a_s;
}
int main(){
  scanf("%lld%lld",&l,&r);//读入区间 
  printf("%lld\n",f_i(r)-f_i(l-1));//找到从头到右区间的所有情况减去左区间 -1 到头的所有情况 
  return 0;
}

花神的数论题

P4317 花神的数论题

遍历每一位，通过枚举 $sum$ 等于的数（在范围内），最后直接快速幂处理值统计即可。

代码

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<stack>
using namespace std;
long long r_r(){//快读 
  long long x=0,d_p=1;
  char c=getchar();
  while(!isdigit(c)){
    if(c=='-')d_p=-1;
    c=getchar();
  }
  while(isdigit(c)){
    x=(x<<1)+(x<<3)+(c^48);
    c=getchar();
  }
  return x*d_p; 
}
const int o_o=51;
const int m_a=1e7+7;
int x[o_o],x_p=0;
long long d_p[o_o][2][o_o][o_o],a_n[o_o],n;
long long k_m(long long a,long long b){//快速幂 
  long long a_s=1;
  while(b){
    if(b&1)a_s=(a_s*a)%m_a;
    a=(a*a)%m_a;
    b>>=1;
  }
  return a_s;
}

//k 当前第几位，u_p 是否为上界，t_p 天了几个 1，d 总共 1 的个数 
long long f_i(int k,int u_p,int t_p,int d){
  if(!k)return t_p==d;//所有位都遍历过了 
  if(d_p[k][u_p][t_p][d]>=0)//已经遍历过了 
    return d_p[k][u_p][t_p][d];
  int l_m=u_p?x[k]:1;//是否为结束位，不是结束位，可以直接赋值为 1 （一定限制小） 
  long long a_s=0;
  for(int i=0;i<=l_m;i++)
    a_s+=f_i(k-1,u_p&&i==l_m,t_p+(i==1),d);//遍历下一位 
  d_p[k][u_p][t_p][d]=a_s;
  return d_p[k][u_p][t_p][d];
}
long long g_a(){
  while(n){//原数改为二进制数 
    if(n&1)x[++x_p]=1;
    else x[++x_p]=0;
    n>>=1;
  }
  for(int i=1;i<=50;i++){
    memset(d_p,-1,sizeof(d_p));//初始化 
    a_n[i]=f_i(x_p,1,0,i);//找 sum(n)=i 的有几个 
  }
  long long a_s=1;//累计答案 
  for(int i=1;i<=50;i++)
    a_s=a_s*k_m(i,a_n[i])%m_a;//sum(n)=1 的有 a_n[i] 个，直接相乘可以用快随幂处理 
  return a_s;
}
int main(){
  n=r_r();
  printf("%lld\n",g_a());
  return 0;
} 

P5308 Quiz（斜率优化）

P5308 COCI2019 Quiz

首先不考虑 $k$，设 $f_i$ 表示从后往前数某一轮还剩 $i$ 个人的最大奖金。
枚举这一轮的下一轮还剩多少人，中间少的就是淘汰的。

$$f_{i}=\max_{0\le j < i}(f_{j}+\frac{i-j}{i})$$

假设对于决策 $0 \le k < j < i$，有 $j$ 优于 $k$。

$f_j+\frac{i-j}{i}>f_k+\frac{i-k}{i}$

$f_j-f_k>\frac{j-k}{i}$

$\frac{f_j-f_k}{j-k}>\frac{1}{i}$

然后既然有了 $k$ 的限制，显然 $WQS$ 二分直接上。

代码

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<stack>
using namespace std;
long long r_r(){//快读 
  long long x=0,d_p=1;
  char c=getchar();
  while(!isdigit(c)){
    if(c=='-')d_p=-1;
    c=getchar();
  }
  while(isdigit(c)){
    x=(x<<1)+(x<<3)+(c^48);
    c=getchar();
  }
  return x*d_p; 
}
const int o_o=1e5+10;
const long double i_p=1e-12;
int n,k,g[o_o];
int q[o_o],h_d,t_l;
long double f[o_o],l,r,m_i;
long double g_f(int x,int y){//获得奖金 
    return(f[x]-f[y])/(x-y);
}
bool g_t(){
  h_d=t_l=1;//初始化 
    q[1]=0;
    for(int i=1;i<=n;++i){
      while(h_d<t_l&&g_f(q[h_d],q[h_d+1])-1.0/i>i_p)h_d++;//能在忍受在范围内，决策更优 
        f[i]=f[q[h_d]]+(long double)(i-q[h_d])/i-m_i;//更新答案 
    g[i]=g[q[h_d]]+1;//需要的轮数 
    while(h_d<t_l&&g_f(q[t_l-1],q[t_l])-g_f(q[t_l],i)<0.0-i_p)--t_l;//回缩一位在可以忍受惹误差范围内，就回缩 
        q[++t_l]=i;//加入当前位 
    }
    return g[n]>=k;//是否在预定内
}
int main(){
    n=r_r(),k=r_r();
    l=0,r=1e6;
    for(int i=1;i<=100;i++){
        m_i=(l+r)/2;
        if(g_t())l=m_i;//不在预定范围内，缩短“战线” 
        else r=m_i;//仍然在，缩短确定范围 
    }
    m_i=l;
  g_t();
    printf("%.9Lf\n",f[n]+k*m_i);//输出结果 
    return 0;
}

状压DP

经常用二进制位存状态。

吃奶酪

P1433 吃奶酪

注意二进制表示是否到过这个奶酪的状态。

例如：现在有 $7$ 个奶酪。

$$a=(1000000)_{2},b=(1001100)_{2}$$

用 $a$ 表示已经走过了第一个奶酪，用 $b$ 表示已经走过了：$1,4,5$ 这些城市。他只是快捷的记录了一种状态

代码

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<stack>
using namespace std;
long long r_r(){//快读 
  long long x=0,d_p=1;
  char c=getchar();
  while(!isdigit(c)){
    if(c=='-')d_p=-1;
    c=getchar();
  }
  while(isdigit(c)){
    x=(x<<1)+(x<<3)+(c^48);
    c=getchar();
  }
  return x*d_p; 
}
const int o_o=3e5+10;
struct po{
  double x;
  double y;
}p_p[31];
double x[21],y[21],f[21][o_o];
double g_l(int a,int b){//两点距离公式 
  return sqrt((p_p[a].x-p_p[b].x)*(p_p[a].x-p_p[b].x)+(p_p[a].y-p_p[b].y)*(p_p[a].y-p_p[b].y));
}
int main(){
    int n=r_r();
    for(int i=1;i<=n;i++)scanf("%lf%lf",&p_p[i].x,&p_p[i].y);//读入奶酪的坐标 
    memset(f,127,sizeof(f));//赋初值 
    for(int s=1;s<=(1<<n)-1;s++)//枚举路径 
      for(int i=1;i<=n;i++){//枚举当前到了哪个点 
          if(!(s&(1<<(i-1))))continue;//如果当前点，不再以经过的路径中，直接返回（不合法） 
          if(s==(1<<(i-1))){//当前点是出发点 
        f[i][s]=0;//赋初值 
        continue;
      }
          for(int j=1;j<=n;j++){//枚举走过的地点，找最优解 
              if(!(s&(1<<(j-1)))||i==j)continue;//没走过这个点，不能自己判自己 
              f[i][s]=min(f[i][s],f[j][s-(1<<(i-1))]+g_l(i,j));//如果找到最小值比当前情况优，及时更新 
          }
      }
    double a_s=-1;//赋初值 
    for(int i=1;i<=n;i++){
        double s=f[i][(1<<n)-1]+g_l(i,0);//已经走过所有路径当前点到最后一个点的距离并统计从出发点到这个点的距离 
        if(a_s==-1||a_s>s) a_s=s;//找最小值 
    }
    printf("%.2lf\n",a_s);//输出 
    return 0;
}

互不侵犯

P1896 SCOI2005 互不侵犯

枚举一行可能出现的所有状况，枚举两行之间所有可能出现的状况拼接，转移并记录。

一定要尝试自己写过。

代码

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<stack>
using namespace std;
long long r_r(){
  long long x=0,f=1;
  char c=getchar();
  while(!isdigit(c)){
    if(c=='-')f=-1;
    c=getchar();
  }
  while(isdigit(c)){
    x=(x<<1)+(x<<3)+(c^48);
    c=getchar();
  }
  return x*f;
}
const int o_o=2001;
int n,k,x_p;
int s_t[o_o],f_s[o_o];
long long d_p[10][o_o][101];
void d_f(int z_t,int s_m,int n_n){//当前格子状态，放的国王数，当前第几个格子
  if(n_n>=n){//记录当前情况的状态 
    s_t[++x_p]=z_t;//记录当前行的国王放置状态 
    f_s[x_p]=s_m;//记录放的国王数 
    return;
  }
  d_f(z_t,s_m,n_n+1);//不用当前格子 
  d_f(z_t+(1<<n_n),s_m+1,n_n+2);//用当前格子，更新状态，更新数量，为了合法性，直接跳过下一个格子的讨论（只能不放） 
}
int main(){
    n=r_r(),k=r_r();
    d_f(0,0,0);//先处理一行的所有可能情况
  for(int i=1;i<=x_p;i++)d_p[1][i][f_s[i]]=1;//将第一行的情况记录 
  for(int i=2;i<=n;i++)//枚举本行所有的情况 
    for(int j=1;j<=x_p;j++)//枚举上一行的所有情况 
      for(int l=1;l<=x_p;l++){//枚举行之间不同的交错转态 
        if(s_t[j]&s_t[l])continue;//上下有重复的国王 
        if((s_t[j]<<1)&s_t[l])continue;//第一个状态所有国王位置左移，如果与第二个状态有位置相同的，说明不合法（第二个转态的右下角有一状态的国王） 
        if(s_t[j]&(s_t[l]<<1))continue;//第二个状态所有国王位置左移，如果与第一个状态有位置相同的，说明不合法（第二个转态的左下角有一状态的国王） 
        for(int s=k;s>=f_s[j];s--)//有继承当前状态的空间 
          d_p[i][j][s]+=d_p[i-1][l][s-f_s[j]];
      }
  long long a_s=0;
  for(int i=1;i<=x_p;i++)a_s+=d_p[n][i][k];//统计所有需要情况（第 n 行，所有可能的国王放置情况，发一共放了 k 的情况数） 
  printf("%lld",a_s); 
    return 0;
}

数据结构优化的dp

二进制优化

在多重背包问题中中尤为凸显。将完全背包转化为 $01$ 背包，大大提升效率，

在 这里 的《宝物筛选》一题中用到了二进制优化。

单调队列优化

选择数字

P2034 选择数字

通过一个手写队列，维护区间最小值，找到最优解，统计即可。

代码

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<stack>
using namespace std;
long long r_r(){
  long long x=0,f=1;
  char c=getchar();
  while(!isdigit(c)){
    if(c=='-')f=-1;
    c=getchar();
  }
  while(isdigit(c)){
    x=(x<<1)+(x<<3)+(c^48);
    c=getchar();
  }
  return x*f;
}
const int o_o=1e5+10;
int n,k;
long long s_m,x_x;
long long p[o_o];//存下标，判断是否进入下一个区间 
long long h_d=1,t_l=1;//队列的首，尾 
long long q[o_o];//队列，存 
long long f[o_o];//前 i 个数被删除的数的最小和 
long long a_s;//答案输出 
int main(){
    n=r_r(),k=r_r();
    for(int i=1;i<=n;i++){//有 n 个整数 
      x_x=r_r();//获取当前值 
      s_m+=x_x;//求所有数的和 
      f[i]=q[h_d]+1ll*x_x;//上个最优的（删的值最小的）加上现在的值（假如删掉现在的值），更新 
      while(h_d<=t_l&&q[t_l]>=f[i])t_l--;//现在的方法更优，将不优的更新掉 
      q[++t_l]=f[i];//将新的产值存入队列 
      p[t_l]=i;//存入当前编号 
      while(h_d<=n&&p[h_d]<i-k)h_d++;//超过这个区间，更新，进入下一个区间（范围 k） 
  }
  for(int i=n-k;i<=n;i++)a_s=max(a_s,1ll*s_m-1ll*f[i]);//用所有数的和，遍历最后一个区间，找最优值 
  printf("%lld",a_s);
    return 0;
}

Power收集

P3800 Power收集

在区间内维护队列，更新最优值，及时判断是否出区间。注意队列存坐标与值两个信息。

代码

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<stack>
using namespace std;
long long r_r(){
  long long x=0,f=1;
  char c=getchar();
  while(!isdigit(c)){
    if(c=='-')f=-1;
    c=getchar();
  }
  while(isdigit(c)){
    x=(x<<1)+(x<<3)+(c^48);
    c=getchar();
  }
  return x*f;
}
const int o_o=4e3+10;
int n,m,k,t,a_s;
int a[o_o][o_o];//读入初始信息 
int d_p[o_o][o_o];//第一维存比那里到哪一行，第二维记录列 
int q_q[o_o][2];//队列 1 存下标，0 存值 
int main(){
    n=r_r(),m=r_r(),k=r_r(),t=r_r();
    for(int i=1;i<=k;++i){//读入有价值得点的信息 
        int x=r_r(),y=r_r();
        a[x][y]=r_r();
    }
    for(int i=1;i<=n;++i){//枚举每一行 
        int h_d=1,t_l=0;//初始化队列头尾 
        for(int j=1;j<=min(m,t);++j){//每句移动位置，注意最多移动 T 格 
            while(q_q[t_l][0]<=d_p[i-1][j]&&h_d<=t_l)--t_l;//有更优方案（值更大），更新 
            q_q[++t_l][0]=d_p[i-1][j];//存入当前值 
            q_q[t_l][1]=j;//保留坐标信息 
        }
        for(int j=1;j<=m;++j){//枚举列（进行移动的结果） 
            if(j+t<=m){//不越界
                while(q_q[t_l][0]<=d_p[i-1][j+t]&&h_d<=t_l)--t_l;//有更优方案（值更大），更新 
                q_q[++t_l][0]=d_p[i-1][j+t];//村入职 
                q_q[t_l][1]=j+t;//保留坐标信息 
            }
            if(q_q[h_d][1]<j-t)++h_d;//判断是否进入到下一个区间 
            d_p[i][j]=q_q[h_d][0]+a[i][j];//更新当前值，最大值加上这个点本身的值 
        }
    }
    for(int i=1;i<=m;++i)//最后一行，以每个点结尾的最大值 
        a_s=max(a_s,d_p[n][i]);
    printf("%d",a_s);//输出最大值 
    return 0;
}