这周讲的东西主要是一些 DP 优化。

1800 文明与法治

题意：你知道未来 TT 天内某只股票的走势，第 ii 天股票买入价为每股 APi\text{AP} _{i}，卖出价为每股 BPi(1≤BPi≤APi≤1000)\text{BP} _{i}(1\le \text{BP} _{i}\le \text{AP} _{i}\le 1000)，同时规定：

  1. 第 ii 天至多购买 ASi\text{AS} _{i} 股，至多卖出 BSi\text{BS} _{i} 股；
  2. 某一天的买入或卖出均算作一次交易在。在两次交易之间至少要间隔 W(0≤W<T≤2000)W(0\le W<T\le 2000) 天；
  3. 任何时候手中的股票数不能超过 MaxP(1≤ASi,BSi≤MaxP≤2000)\text{MaxP}(1\le \text{AS} _{i},\text{BS} _{i}\le \text{MaxP} \le 2000)。

在第 11 天之前假设你有无限数目的钱，但是没有任何股票。请问 TT 天后你最多能赚到多少钱？

解析：原题为[SCOI2010]股票交易。

一道经典的单调队列 DP。假设 fi,jf _{i,j} 为第 ii 天有 jj 只股票时赚得的最多的钱，那么 fT,0f _{T,0} 即是答案，因为最后一天前把股票卖完肯定更优。

那么考虑如何转移。如果第 ii 天不进行交易，则

fi,j=fi−1,jf _{i,j}=f _{i-1,j}

否则，可分成买入或卖出两种交易。若在第 ii 天买入股票，则

fi,j=max⁡max⁡(0,j−ASi)≤k<j(fi−W−1,k−(j−k)×APi)=max⁡max⁡(0,j−ASi)≤k<j(fi−W−1,k+k×APi)−j×APi\begin{aligned} f _{i,j} & =\max _{\max(0,j-\text{AS} _{i})\le k<j}(f _{i-W-1,k}-(j-k)\times \text{AP} _{i})\\ & = \max _{\max(0,j-\text{AS} _{i})\le k<j}(f _{i-W-1,k}+k\times \text{AP} _{i})-j\times \text{AP} _{i} \end{aligned}

即从 kk 只股票买入到 jj 只股票。同理，若卖出股票，则

fi,j=max⁡j<k<min⁡(j+BSi,MaxP)(fi−W−1,k+(k−j)×BPi)=max⁡j<k<min⁡(j+BSi,MaxP)(fi−W−1,k+k×BPi)−j×BPi\begin{aligned} f _{i,j} & =\max _{j< k <\min(j+\text{BS} _{i},\text{MaxP})}(f _{i-W-1,k}+(k-j)\times \text{BP} _{i})\\ & = \max _{j< k <\min(j+\text{BS} _{i},\text{MaxP})}(f _{i-W-1,k}+k\times \text{BP} _{i})-j\times \text{BP} _{i} \end{aligned}

即从 kk 只股票卖出到 jj 只股票。

现在考虑初始状态如何设置。由于第一天前有无限的钱，因此这 TT 天内的任何一天都可以作为交易的第一天，买入至多 ASi\text{AS} _{i} 只股票。即

fi,j=−j×APi(0≤j≤ASi)f _{i,j}=-j\times \text{AP} _{i}(0\le j\le \text{AS} _{i})

同时将其他状态都赋成极小值。

如果暴力转移以上方程，复杂度为 O(T⋅MaxP2)O(T\cdot \text{MaxP} ^{2})，无法接受。观察转移方程，容易发现要求的是关于 kk 的一段区间内的某个最大值，这个区间随着 jj 向前移动。即经典的滑动窗口问题，可以用单调队列维护来优化 DP，于是复杂度就降到了 O(T⋅MaxP)O(T\cdot \text{MaxP})，可以通过这道题。

代码：

//
// Created by 屋顶上的小丑 on 2023/3/13.
//
#include<cstdio>
#include<cstring>
const int maxn=2e3;
int T,MaxP,W,q[maxn+5];
int ap[maxn+5],bp[maxn+5];
int as[maxn+5],bs[maxn+5];
long long f[maxn+5][maxn+5];
int max(int a,int b)
{
    return (a>b)?a:b;
}
int main()
{
    scanf("%d%d%d",&T,&MaxP,&W);
    for(int i=1;i<=T;i++)
        scanf("%d%d%d%d",&ap[i],&bp[i],&as[i],&bs[i]);
    memset(f,-0x3f,sizeof(f));
    for(int i=1;i<=T;i++)
        for(int j=0;j<=as[i];j++)
            f[i][j]=-j*ap[i];
    for(int i=1;i<=T;i++)
    {
        for(int j=0;j<=MaxP;j++)
            f[i][j]=max(f[i][j],f[i-1][j]);
        if(i<=W)
            continue;
        int las=i-W-1;
        int l=1,r=0;
        for(int j=0;j<=MaxP;j++)
        {
            while(l<=r&&q[l]<j-as[i]) l++;
            if(l<=r)
                f[i][j]=max(f[i][j],f[las][q[l]]+(q[l]-j)*ap[i]);
            while(l<=r&&f[las][q[r]]+q[r]*ap[i]<=f[las][j]+j*ap[i]) r--;
            q[++r]=j;
        }
        l=1,r=0;
        for(int j=MaxP;j>=0;j--)
        {
            while(l<=r&&q[l]>j+bs[i]) l++;
            if(l<=r)
                f[i][j]=max(f[i][j],f[las][q[l]]+(q[l]-j)*bp[i]);
            while(l<=r&&f[las][q[r]]+q[r]*bp[i]<=f[las][j]+j*bp[i]) r--;
            q[++r]=j;
        }
    }
    printf("%lld",f[T][0]);
    return 0;
}

1511 wennitao卖冰墩墩

题意：一条路上有 n(1≤n≤106)n(1\le n\le 10 ^{6}) 个工厂，第 ii 个工厂距离第 11 个工厂 xix _{i}，有 pip _{i} 个冰墩墩，在这里搭建售卖点的费用为 ci(0≤xi,pi,ci<231)c _{i}(0\le x_{i},p _{i},c _{i}<2 ^{31})，保证 xi<xi+1x _{i}<x_{i+1}。现在希望把所有的冰墩墩运往售卖点售卖，只能从编号小的工厂运往编号大的工厂，一个冰墩墩运送一个单位距离费用为 11，请问在哪写地方搭建售卖点能够使总费用最小？

解析：非常经典的斜率优化。

设 fif _{i} 表示最后一个售卖点在第 ii 个工厂的最小费用，可以得到转移方程：

fi=min⁡0≤k<i(fi,fk+ci+∑j=k+1ipj⋅(xi−xj))f _{i}=\min _{0\le k < i}(f _{i},f _{k}+c _{i}+\sum _{j=k+1} ^{i}p _{j}\cdot (x _{i}-x _{j}))

设 pip _{i} 前缀和为 sumi1sum ^{1} _{i}，pi⋅xip _{i}\cdot x _{i} 前缀和为 sumi2sum _{i} ^{2}，则

fi=min⁡0≤k<i(fi,fk+ci+xi⋅(sumi1−sumk1)−(sumi2−sumk2))f _{i}=\min _{0\le k < i}(f _{i},f _{k}+c _{i}+x _{i}\cdot (sum _{i} ^{1}-sum _{k} ^{1})-(sum _{i} ^{2}-sum _{k} ^{2}))

这里已经可以看出斜率优化的雏形了，我们继续转化，令 ai=ci+xi⋅sumi1−sumi2,bi=fi+sumi2a _{i}=c _{i}+x _{i}\cdot sum _{i} ^{1}-sum _{i} ^{2},b _{i}=f _{i}+sum _{i} ^{2}，则上式为

fi−ai=min⁡0≤k<i(fi,bk−sumk1xi)f _{i}-a _{i}=\min_{0\le k<i}(f _{i},b _{k}-sum _{k} ^{1}x _{i})

设 x=sumk1,k=xi,y=bk,B=fi−aix=sum _{k} ^{1},k=x _{i},y=b _{k},B=f _{i}-a _{i}，即 B=−kx+yB=-kx+y，到这里已经完全可以看出这就是裸的斜率优化了。由于要求 min⁡\min 值，而斜率 k=xik=x _{i} 单调递增，横坐标 x=sumk1x=sum _{k} ^{1} 也是单调递增的，因此直接用单调队列维护一个下凸包即可。复杂度为 O(n)O(n)。

代码：

//
// Created by 屋顶上的小丑 on 2023/3/13.
//
#include<cstdio>
#include<cstring>
const int maxn=1e6;
int n,x[maxn+5],p[maxn+5];
int q[maxn+5],c[maxn+5];
long long sum1[maxn+5],sum2[maxn+5];
long long f[maxn+5];
long long a(int i)
{
    return c[i]+x[i]*sum1[i]-sum2[i];
}
long long b(int i)
{
    return f[i]+sum2[i];
}
double k(int i)
{
    return (double)x[i];
}
long long X(int i)
{
    return sum1[i];
}
long long Y(int i)
{
    return b(i);
}
double slope(int i,int j)
{
    return (double)(Y(i)-Y(j))/(X(i)-X(j));
}
long long min(long long x,long long y)
{
    return (x<y)?x:y;
}
int main()
{
    scanf("%d",&n);
    f[0]=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d%d",&x[i],&p[i],&c[i]);
        sum1[i]=sum1[i-1]+p[i];
        sum2[i]=sum2[i-1]+1ll*p[i]*x[i];
    }
    int l=1,r=1;
    for(int i=1;i<=n;i++)
    {
        while(l<r&&slope(q[l],q[l+1])<k(i)) l++;
        f[i]=b(q[l])+a(i)-1ll*sum1[q[l]]*x[i];
        while(l<r&&slope(q[r-1],q[r])>slope(q[r],i)) r--;
        q[++r]=i;
    }
    printf("%lld",f[n]);
    return 0;
}

1802 破败的灯塔国(加强版)

题意：一条直线上有 n(0<n≤106)n(0<n\le 10 ^{6}) 座连续的山峰，第 ii 座山峰高度为 hi(0<hi≤109)h _{i}(0<h _{i}\le 10 ^{9})。若在第 ii 座山峰建立一座高度为 p(p≥0,p∈Z)p(p\ge 0,p\in \Z) 的灯塔，它能照亮第 jj 座山峰当且仅当 hj≤hi+p−∣i−j∣h _{j}\le h_{i}+p-\sqrt{|i-j|}。现在请问在每座山峰上建立一座灯塔，想要让它照亮所有山峰的最小高度是多少。

解析：原题为[JSOI2016]灯塔。

设第 ii 座山峰建立灯塔的最小高度为 fif _{i}，那么显然

fi=max⁡1≤j≤n,j≠i(hj−hi+∣i−j∣)=max⁡1≤j≤n,j≠i(hj+∣i−j∣)−hi\begin{aligned} f _{i}&=\max _{1\le j\le n,j\neq i}(h _{j}-h _{i}+\sqrt{|i-j|})\\ &=\max _{1\le j\le n,j\neq i}(h _{j}+\sqrt{|i-j|})-h _{i} \end{aligned}

我们只考虑 j<ij<i 的情况，因为对于 j>ij>i 的情况我们只用反过来再做一遍即可。

然后就能发现决策单调性了。由于 x+1−x<x−x−1\sqrt{x+1}-\sqrt{x}<\sqrt{x}-\sqrt{x-1}，因此当决策点 j<kj<k 时，满足 i+1−j−i−j≤i+1−k−i−k\sqrt{i+1-j}-\sqrt{i-j}\le\sqrt{i+1-k}-\sqrt{i-k}，即 i+1−j+i−k≤i+1−k+i−j\sqrt{i+1-j}+\sqrt{i-k}\le\sqrt{i+1-k}+\sqrt{i-j}，满足四边形不等式。然后就很好处理了，用二分栈或者分治都能实现，复杂度为 O(nlog⁡n)O(n\log n)。代码是分治写法。

代码：

//
// Created by 屋顶上的小丑 on 2023/3/13.
//
#include<cstdio>
#include<cmath>
const int maxn=1e6;
int n,h[maxn+5];
double ans[maxn+5];
inline double max(double a,double b)
{
    return a>b?a:b;
}
inline double calc(int i,int j)
{
    return h[j]+sqrt(abs(i-j));
}
template<class T>
void swap(T &x,T &y)
{
    T temp=x;
    x=y;
    y=temp;
}
void solve(int l,int r,int L,int R)
{
    if(l>r)
        return ;
    int mid=(l+r)>>1,pos=0;
    double las=0;
    for(int i=L;i<=mid&&i<=R;i++)
    {
        double now=calc(mid,i);
        if(las<now)
        {
            las=now;
            pos=i;
        }
    }
    ans[mid]=max(ans[mid],las);
    solve(l,mid-1,L,pos);
    solve(mid+1,r,pos,R);
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&h[i]);
    solve(1,n,1,n);
    for(int i=1;i<=n/2;i++)
    {
        swap(h[i],h[n-i+1]);
        swap(ans[i],ans[n-i+1]);
    }
    solve(1,n,1,n);
    for(int i=n;i>=1;i--)
        printf("%d\n",(int)ceil(ans[i]-h[i]));
    return 0;
}

1812 zhongzero的黑白树

题意：给定一个 n(1≤n≤5×104)n(1\le n\le 5\times 10 ^{4}) 个点 m(1≤m≤105)m(1\le m\le 10 ^{5}) 条边无向带权连通图，每条边是黑色或白色，让你求恰好有 KK 条白色边的最小权生成树，输出该生成树的边权和即可。

解析：原题为[国家集训队]Tree I。

挺简单的题，用到了类似 wqs 二分（因为感觉并不算严格的 wqs 二分）的思路。

要求最小权生成树，显然要用最小生成树算法。我们思考一下 kruskal 算法求解最小生成树的原理，它需要先按边权从小到大进行排序再依次对边进行选择，边权越小的边会优先被选择。因此我们可以通过改变白边的权值来改变它们被选中的机会。我们考虑二分一个额外值 Δ\Delta，将白边的权值全部加上 Δ\Delta 再跑 kruskal，如果最后跑出的结果中白边数量小于 KK，说明我们的 Δ\Delta 太大了，把它调小；反之则可以将 Δ\Delta 调大。由于数据一定有解，如此一定能够得到一个恰好 KK 条白边的最小权生成树，此时将得到的边权和减去 K⋅ΔK\cdot \Delta 即是答案。

//
// Created by 屋顶上的小丑 on 2023/3/13.
// 第四道题，用了algorithm库中的sort
//
#include<cstdio>
#include<cmath>
#include<algorithm>
#define INF 1e9
using namespace std;
const int maxn=1e5;
struct edge
{
    int x;
    int y;
    int z;
    int col;
}s[maxn+5];
bool cmp(edge a,edge b)
{
    if(a.z==b.z)
        return a.col<b.col;
    return a.z<b.z;
}
int n,m,need,maxx,k;
int fa[maxn+5],ans,sum;
int getfa(int x)
{
    if(fa[x]==x)
        return x;
    return fa[x]=getfa(fa[x]);
}
bool check(int x)
{
    for(int i=1;i<=m;i++)
        if(!s[i].col)
            s[i].z+=x;
    for(int i=1;i<=n+1;i++)
        fa[i]=i;
    sum=k=0;
    sort(s+1,s+m+1,cmp);
    int tot=0;
    for(int i=1;i<=m;i++)
    {
        if(tot==n-1)
            break;
        int a=getfa(s[i].x);
        int b=getfa(s[i].y);
        if(a==b)
            continue;
        else
        {
            tot++;
            fa[a]=b;
            sum+=s[i].z;
            k+=(s[i].col^1);
        }
    }
    return k>=need;
}
void clean(int x)
{
    for(int i=1;i<=m;i++)
        if(!s[i].col)
            s[i].z-=x;
}
int main()
{
    scanf("%d%d%d",&n,&m,&need);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d%d",&s[i].x,&s[i].y,&s[i].z,&s[i].col);
        s[i].x++;
        s[i].y++;
        maxx=max(maxx,s[i].z);
    }
    int l=-INF,r=INF,mid;
    while(l<=r)
    {
        mid=(l+r)>>1;
        if(check(mid))
        {
            ans=sum-need*mid;
            l=mid+1;
        }
        else
            r=mid-1;
        clean(mid);
    }
    printf("%d\n",ans);
    return 0;
}