DP选讲

本文主要是介绍DP选讲，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

$DP$选讲

直接上题吧

放个题单

[各省省选DP](https://www.luogu.com.cn/training/151079)

$P5322[BJOI2019]$排兵布阵

一眼题,考虑$dp[i][j]$表示已经确定前$i$个的选的数量$j$的最大收益,考虑怎么转移

直接转移这一维和上一维的数量,枚举复杂度$O(n\times m^2)$

那么显然的是直接枚举有很多状态无用,那么有用的决策点只有$k$个

那么直接枚举决策点,那么非决策点必定不优,显然的是就是你在两个决策点之间

花费是无用的,那么复杂度变为$O(n\times m\times k)$

#include<bits/stdc++.h>
#define MAXM 20005
#define MAXN 150
using namespace std;
inline int rd(){
    int x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
int jc[MAXN][MAXN];
int a,s,n,m,val[MAXN][MAXN],dp[2][MAXM];
int main()
{
    cin>>s>>n>>m;
    for(int i=1;i<=s;i++)
    {
        for(int j=1;j<=n;j++)
        {
            a=rd();
            jc[j][i]=a;
        }
    }
    for(int i=1;i<=n;i++)
    {
        sort(jc[i]+1,jc[i]+1+s);
        for(int j=1;j<=s;j++)
        {
            val[i][j]=2*jc[i][j]+1;
        }
    }
    for(int i=1;i<=n;i++)
    {
        int now=(i&1),pre=(now^1);
//        memset(dp[now],0xcf,sizeof(dp[now]));
        for(int k=0;k<=s;k++)
        {
            for(int j=0;j<=m;j++)
            {
                if(j<val[i][k])
                {
                   dp[now][j]=max(dp[now][j],dp[pre][j]);
                }
                else
                {
                    dp[now][j]=max(dp[now][j],max(dp[pre][j],dp[pre][j-val[i][k]]+i*k));
                }
            }
        }
//        for(int j=0;j<=m;j++)
//        {
//            cout<<dp[now][j]<<" ";
//        }
//        cout<<endl;
    }
    cout<<dp[n&1][m]<<endl;
}
/*
1 3 10
2 2 6

./a.exe<a.in>a.out

2 3 10
2 2 6
0 0 0
*/

$BJOI[2019]$奥术神杖

上来第一眼没有思路,由于直接$DP$显然不好求解,而且这个记录贡献的方式很生草

先考虑如果确定了最后状态,那么答案怎么求$?$

$\sqrt{\Pi_{i=1}^{|s|}v[i]}^{|s|}$

就是把所有出现的咒语乘起来,对总次数开根号

套路,取$log$

那么式子变为

$Ans=log(\sqrt{\Pi_{i=1}^{|s|}v[i]}^{|s|})$

$Ans=log((\Pi_{i=1}^{|s|}v[i])^\frac{1}{|s|})$

$Ans=\frac{1}{|s|}log(\Pi_{i=1}^{|s|}v[i])$

$Ans=\frac{1}{|s|}\sum_{i=1}^{|s|}log(v[i])$

(不得不说$log$乘法转加法真的很好用)

再次发现,这个东西无法直接转移

以我的理解是这个不满足最优子问题结构,无法设计一个好的状态去转移,就是说你用这个状态无法能去转移

就是无法设计一个状态去转移,就是即使你设计$dp[i][j]$也无法完整考虑个数这个问题

而且你次数与次数之间没办法转移,即使你当前保证是当前乘积最大值,也不能开完之后还是最大值

或许你可以换个状态,$dp[i][j]$表示确定了$i$位,匹配$j$个的乘积最大值

发现没办法转移,你需要确定这一位,然后并不知道匹配了多少个

你又说,再多设一维,并且把$dp$设在$AC$自动机上

$dp[i][j][k]$表示目前确定了$i$位,已经匹配了$j$个,目前在$AC$自动机的第$k$个节点的最大乘积

大概的转移方式就是$dp[i+1][j+val[y]][y]=dp[i][j][k]$

结果发现这个可以转移。。。但是你看看这个复杂度就很不友好

在极限数据下的话$dp$状态数是$O(n\times n^2\times cnt)$

分别是$n$个位置,一共所有可能匹配数目$n^2$,和$AC$自动机的节点数

那么用一个很好的套路,对于这种样子带着小数的$dp$,显然可以想到分数规划

然后判断是否合法吧

那么就是这个样子$\frac{1}{|s|}\sum_{i=1}^{|s|}log(v[i])>=mid$

$\sum_{i=1}^{|s|}(log(v[i])-mid)>=0$

那么对于每个贡献$-=mid$,然后转移这个式子的最大值,判断是否大于$0$

发现一个很有意思的事情,这个式子不存在那个烦人的开根号,只需要累和就好了

然后这个也不必关心匹配了几个,只需要一直累加就好了,貌似就解决了

大概重新透彻了分数规划的意义,就是某些状态转移需要和数量或其他有关联

那么就分数规划化简式子,换一种统计方法得到最优

也就是这道题,直接转移不好写,化简完式子之后发现只需要发现有了一个新的匹配直接加上新的匹配的贡献就好了

这个也很好的解决了,式子本身含义也是所有出现的贡献累加起来

这个式子的最大值很好转移

设$dp[i][j]$表示目前已经确定了$i$位,转移到了第$j$个节点的这个式子的最大值

那么转移的话也很简单了

而且这样转移和$AC$自动机匹配性质一样,显然可以得到所有的状态,而且贡献正确

#include<bits/stdc++.h>
#define INF 2147473647
#define MAXN 2005
using namespace std;
const double eps=1e-5;
int tr[MAXN][15],End[MAXN],fail[MAXN],cnt,n;
int zy[MAXN][MAXN][2];
double F[MAXN][MAXN],val[MAXN];
char T[MAXN];
void Insert(char *s,double w)
{
     int now=0;
     for(int i=1;s[i];i++)
     {
          if(!tr[now][s[i]-'0'])
          {
             tr[now][s[i]-'0']=++cnt;    
         }
         now=tr[now][s[i]-'0'];
     }
     End[now]++;
     val[now]+=w;
}
void Get_fail()
{
     queue<int>q;
     int now=0;
     for(int i=0;i<10;i++)
     {
         if(tr[now][i])
         {
             q.push(tr[now][i]);
         }    
     }    
     while(!q.empty())
     {
            int now=q.front();
            End[now]+=End[fail[now]];
            val[now]+=val[fail[now]];
            q.pop();
            for(int i=0;i<10;i++)
            {
                   if(tr[now][i])
                   {
                      fail[tr[now][i]]=tr[fail[now]][i];
                  q.push(tr[now][i]);    
               }
               else
               {
                     tr[now][i]=tr[fail[now]][i];
               }
           }
     }
}
char Ans[MAXN];
double dp(double v)
{
       for(int i=0;i<=cnt;i++)
       {
              val[i]-=End[i]*v;
       }
       for(int i=0;i<=n;i++)
       {
              for(int j=0;j<=cnt;j++)
              {
                  F[i][j]=-1e100;    
           }
       }
       F[0][0]=0;
       for(int i=0;i<n;i++)
       {
              for(int j=0;j<=cnt;j++)
              {
                     if(F[i][j]>-1e99)
                     {
                           for(int k=0;k<10;k++)
                           {
                               if(T[i]!='.'&&T[i]!=k+'0') continue;
                               int y=tr[j][k];
                               if(F[i+1][y]<F[i][j]+val[y])
                               {
                                  F[i+1][y]=F[i][j]+val[y];
                         zy[i+1][y][0]=j;
                         zy[i+1][y][1]=k;
                         //¼Ç¼תÒƵã
                      }
                  }
               }
           }
       }
       for(int i=0;i<=cnt;i++)
       {
              val[i]+=End[i]*v;
       }
       int pos=0;
       for(int i=1;i<=cnt;i++)
       {
           if(F[n][i]>F[n][pos]) pos=i;
       }
       for(int i=n,now=pos;i;i--)
       {
              Ans[i]=zy[i][now][1]+'0';
              now=zy[i][now][0];
       }
       return F[n][pos];
}
int m,v;
char s[MAXN];
int main()
{
    cin>>n>>m;
    scanf("%s",T);
    for(int i=1;i<=m;i++)
    {
        scanf("%s",s+1);
        scanf("%d",&v);
        Insert(s,log(v));
    }
    Get_fail();
    double l=0,r=log(INF),res=0;
    while(r-l>eps)
    {
          double mid=(l+r)/2.0;
          if(dp(mid)>0) res=mid,l=mid;
          else r=mid;
    }
    dp(res);
    printf("%s",Ans+1);
}

$ZJOI2019$线段树

也不知道$ZJ$出题人怎么想的,一天三道题都是$DP$

这个还是比较简单了

一个很显然的套路,就是可以考虑换一种枚举方式统计贡献

这个不是每个线段树有多少节点被打标记吗

转化思路为这个节点被多少个线段树打标记去累和

那么$dp[i][j]$表示第$i$个节点在前$j$次复制后有多少个被打标记

那么转移就很显然了

//真是不知道能在线段树上跑DP的出题人怎么想
//首先,这个东西肯定不能每次都重开线段树
//那么在一棵线段树上转移
//dp[now][i]当前节点在前i次操作覆盖了几次
//那么这么显然可以直接转移吧
//我们相当于知道了前面所有线段树的这个点状态
//那么由于转移是独立的,那么该咋搞咋搞
//我在想这个东西貌似不太对,就是说会不会出现
//貌似没有影响,因为不会出现标记为2
//我貌似又忘记一个东西叫,贡献独立
//既然整体不好搞,那我们很显然可以单独计算每一个贡献累加
#include<bits/stdc++.h>
#define int long long
#define mod 998244353
#define MAXN 200005
#define ls (now<<1)
#define rs ((now<<1)|1)
using namespace std;
struct node
{
       int l,r,sum;
}tr[MAXN<<2];
int f[MAXN<<2],g[MAXN<<2],tf[MAXN<<2],tg[MAXN<<2],cnt;
void build(int now,int l,int r)
{
     tr[now].l=l,tr[now].r=r;
     f[now]=0;
     g[now]=1;
     tf[now]=1;
     tg[now]=1;
     if(l==r) return ;
     int mid=(l+r)>>1;
     build(ls,l,mid);
     build(rs,mid+1,r);
}
void pdTf(int now,int x)
{
     (tr[now].sum*=x)%=mod;
     (tf[now]*=x)%=mod;
     (f[now]*=x)%=mod;
}
void pdTg(int now,int x)
{
     (tg[now]*=x)%=mod;
     (g[now]*=x)%=mod;
}
void pd(int now)
{
     if(tf[now]!=1)
     {
        pdTf(ls,tf[now]);
        pdTf(rs,tf[now]);
        tf[now]=1;         
     }
     if(tg[now]!=1)
     {
        pdTg(ls,tg[now]);
        pdTg(rs,tg[now]);
        tg[now]=1;         
     }
}
void push_up(int now)
{
     tr[now].sum=(f[now]+tr[ls].sum+tr[rs].sum)%mod;
}
void change(int now,int l,int r)
{
     pd(now);
     if(tr[now].l==l&&tr[now].r==r)
     {
         f[now]=(f[now]+cnt)%mod;
         g[now]=g[now]%mod;
         pdTf(ls,2);
         pdTf(rs,2);
     }
     else
     {
        int mid=(tr[now].l+tr[now].r)>>1;
        g[now]=(g[now]+cnt)%mod;
        if(r<=mid)
        {
             change(ls,l,r);
             pd(rs);
             f[rs]=(f[rs]+cnt+mod-g[rs])%mod;
             g[rs]=(g[rs]+g[rs])%mod;
             pdTf(rs<<1,2);pdTg(rs<<1,2);
             pdTf(rs<<1|1,2);pdTg(rs<<1|1,2);
             push_up(rs);
        }
        else if(l>mid)
        {
                change(rs,l,r);
             pd(ls);
             f[ls]=(f[ls]+cnt+mod-g[ls])%mod;
             g[ls]=(g[ls]+g[ls])%mod;
             pdTf(ls<<1,2);pdTg(ls<<1,2);
             pdTf(ls<<1|1,2);pdTg(ls<<1|1,2);
             push_up(ls);
        }
        else
        {
            change(ls,l,mid);
            change(rs,mid+1,r);
        }
      }
     push_up(now);    
}
int n,m,opt,l,r;
signed main()
{
    cin>>n>>m;
    build(1,1,n);
    cnt=1;
    for(int i=1;i<=m;i++)
    {
        cin>>opt;
        if(opt==1)
        {
            cin>>l>>r;
            change(1,l,r);
            cnt=(cnt+cnt)%mod;
        }
        if(opt==2)
        {
           cout<<tr[1].sum<<endl;
        }
    }
}

这篇关于DP选讲的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！