DP选讲

懵逼 啥玩意 DP

---

常见dp优化

• 决策单调性：二分

• 前缀和与前缀最大值优化

• 斜率优化

• 矩阵乘法快速幂优化

• 数据结构优化

单调队列优化

单调队列模板

//L为头，R为尾，初始L=1,R=0
void Insert(int x){
    while(l<=r&&a[r]<=x) r--;
    //由于寻找次数一定小于插入长度，所以保证复杂度O(n)
    s[++r]=x;
}
void Query(){
    return s[l];
}
void Delete(){
    //判断是否在单调队列中
    cnt++;
    if(t[l]==cnt) l++;
}
int main(){
    cin>>Q;
    while(Q--){
        cin>>A;
        if(A==1){
            cin>>x;
            Insert(x)
        }
        if(A==2){
            cout<<Query()<<endl;
        }
        if(A==3){
            Delete();
        }
    }
}

多重背包

$O(n^3)$，将物品拆开
$O(n^2logn)$，将物品按照$2^k$拆开
$O(nm)$，单调队列
先枚举所有物品，再枚举所有可能情况，那么换一种写法：

--仍然是伪代码
v[i]来表示第i个物品的价值  w[i]来表示体积
for (int i=1; i<=n; i++)
  for (int k=0; k<=m; k++)
    for (int j=0; j<=c[i]; j++)
      if (k>=j*w[i])
        dp[i][k]=max(dp[i][k],dp[i-1][k-j*w[i]]+j*v[i])

来看红与蓝色，那么后一个转移来源与前一个的区别就是新添了一个少了一个，也就是线性维护这样几个操作：
插入队首元素
取出最大的元素
弹出队尾元素
就是单调队列

烽火传递

给定n个非负整数，选择其中若干数字，使得每连续k个数中至少有一个数被选出。要求选择的数字之和尽可能小。n<=1000。

dp[i]表示1~i是被选出的，那么dp[i]=min{dp[j]}+a[i]且$j\in[i-k,i-1]$
而每次转移只相差了a[i-k+1]与a[i+1]两个数，那么就是用一个线性结构维护这个操作，
这就是单调队列，也就是烽火传递可以O(n)实现

--还是伪代码
for(int i=l;i<=k;++i) dp[i]=a[i];
for(int i=0;i<k;++i) push(dp[i]);//压入
for(int i=k;i<=n;++i){
    dp[i]=query()+a[i];//找最小值 
    push(dp[i]);
    pop();//删除队尾 
} 

也就是，一个dp值有c[i]个等差数列推得，而转移以min/max移动
通式：dp[i][j]=min{dp[i-1][k]}

最大子段和

• dp
  见今天的题解
• 贪心

for (int i=1; i<=n; i++)
{
  sum+=a[i];
  if (sum<0) sum=0;
  MAX=max(MAX,sum);
}
cout<<MAX;

• 前缀和

for (int i=1; i<=n; i++) 
    s[i]=s[i-1]+a[i];
for (int i=1; i<=n; i++)
{
  ans=max(ans,s[i]-MIN);
  MIN=min(MIN,s[i]);
}

任何一段区间[L,R]相当于S[R]-S[L-1]，我们就是找到最大的S[R]与最小的S[L-1]，用min记录一下。

加强版 成环

• 拉开拼成一个
  这个做法翻车了，233333
• 单调队列
  对于前缀和的做法枚举r时，随着r不断增加，右端点与左端点都会增加，然后用单调队列维护这一操作

装喷头

有一根长为n的数轴，要在这根数轴上装一些喷头，每个喷头的喷射半径在[a,b]之间并可调节。
其中有m个限制，形如li,ri，表示[li,ri]这一段区间的整点一定要同时被一个喷头喷到。
规定每个整点位置恰好被一个喷头喷到，并且喷头不允许喷出外。问至少装几个喷头。
n<=1000。

用dp[i]表示第i个位置装喷头，1~i都满足条件这样的最少喷头数量
这么搞转移列不出来
用dp[i]表示前i个位置都满足条件了，最少装多少喷头，dp[j]表示1~j都满足条件了，j+1~i没满足条件，装个喷头要恰好覆盖这些
由于喷头的喷水半径是个圆，所以2a<=i-j<=2b
因此dp[i] = min{dp[j]}+1 2a<=i-j<=2b
j的取值是有$l_i,r_i$确定的，所以j是由区间构成的
标记时，若$i\in[l,r-1]$那么dp[i]=inf.

for (int i=1; i<=n; i++)
{
  if (!v[i]) dp[i]=inf; 
  else 
  {
    dp[i]=Query()+1;
  }
  Insert(dp[i+1-2a]);
  Delete(dp[i-2b]);
}

NOI2005 瑰丽华尔兹

在一个n*m的矩阵上，有一些点是障碍，有一些点是空地。并且有一个点有个人。
这个人在[L1,R1]个时刻会向X1行动，[L2,R2]个时刻会向X2行动以此类推。总共有T段区间，且L[i+1]=R[i]+1，L[1]=1。
其中X1,X2,…,XT为上下左右中的一种。
为了使这个人在移动过程中不撞掉也不掉出矩阵，每次可以选择耗费1点能量让它不动，问最少耗费多少能量使得它再R[T]这个时刻还在这个矩阵上。
n,m<=200，T<=200，R[T]<=40000。

dp[i][j][k]第i时刻在(j,k)
枚举第i时刻用不用能量，可以转移为dp[i][j+v[i]][k+v[i]]
正确性可以保证，状态数比较大
枚举第i区间结束时在(j,k)用的能量
那么就是max{dp[i-1][j][k-x]+(t[i]-x)}（t[i]-x表示用了多少能量）
复杂度$O(n^4)$
用dp[i][j][k]表示第i个区间结束时最多走了多少步
以右方向为例来分析这个问题
那么$dp[i][j][k]=max{dp[i-1][j][k-x]+x}(k\in [0,t])$t表示该时间段的时间且中途无障碍
即k>=k-x>=k-t也就是在[k-t,k]中转移
随k增加，让左右端点分别移动，这就是一个单调队列。
问题的关键是障碍，随着k的增加，会遇到障碍。如果走到障碍，本次不转移，左右端点分别移动到k+1，方便下一次运行。
具体实现时，由于由于要加x，就可以将队列中所有元素增加一，用一个变量维护一下。
然后是zhw本人的解释：

dp[i][j][k] 第i个时间段结束，人在(j,k)这个位置，这样子最多走多少步
假设 i这个时间段 这个人会往右走 // t=这一个时间段有多少时间
dp[i][j][k]=max{dp[i-1][j][k-x]+x} 0<=x<=t。(j,k-x)~(j,k) 没有障碍物
k-t<=p<=k 并且 (j,p)~(j,k)没有障碍物
dp[i][j][k]=max{dp[i-1][j][p]+x} k-t<=p<=k 并且 (j,p)~(j,k)没有障碍物
随着k的增加 k-t,k都一定会增加 单调队列
维护能更新的这个区间会怎么移动。 [l,r]
每次在插入进队列之前，把队列中所有元素+1，这件事是可以通过一个变量来维护的。
T*n^3
i这个时间段 这个人会往左、下、上走

一道神题

一个n*n的矩阵，每行每列恰好放两个棋子，问方案总数%p的值

似乎不能OEIS

似乎是本蒟蒻听懂的唯一一道题
dp[i][j][k]表示前i行有j列放了一个棋子，k列没有放棋子
对i+1行来说，
(0,0)表示放的两列之前都没放，则转化为dp[i+1][j+2][k-2]
(0,1)表示放的两列一个放过一个没放，则转化为dp[i+1][j][k-1]
(1,1)表示放的两列之前都放过一个，则转化为dp[i+1][j-2][k]

显然，
$dp[i+1][j+2][k-2]+=dp[i][k][j]*C_k^2$
$dp[i+1][j][k-1]+=dp[i][k][j]*j*k$
$dp[i+1][j-2][k]+=dp[i][k][j]*C_j^2$
结果就是dp[n][0][0]
这样就是$O(n^3)$的做法。
再来思考一下，ijk之间有这样的关系
$n-\dfrac{2i-j}{2}-j=k$
所以这里可以二维优化一维:
$dp[i+1][j+2]+=dp[i][j]*C_k^2;$
$dp[i+1][j-2]+=dp[i][j]*C_j^2;$
$dp[i+1][j]+=dp[i][j]*j*k;$
结果就是dp[n][0]
复杂度$O(n^2)$
如何达到O(n)的复杂度呢？
以块为单位，用dp[i]表示i*i的矩阵满足条件的方案总数
观察最后一列，前两个和任意两个是没有区别的
例如下图，这两种状态实质是相同的。

$dp[i]=C_i^2*g[i]$，g(i)表示第一行第n个第二行第n个都放了的总数
而对于g[i]，如果第一行和第二行其它棋子在同一列，那么g[i]+=dp[i-2]*(i-1)，如下图

否则，如下图，每一个状态移上去就可以满足了。即g[i]+=dp[i-1]*2.

将上述结合一下，

$$dp[i]=C_i^2*(dp[i-2]*(i-1)+dp[i-1]*2)$$
我们完成了一个O(n)的方程。
综上所述，我们其实可以采用这样一种思路：

将原问题化简为与原问题相似规模较小的问题