dp 优化
\(\text{By DaiRuiChen007}\)
I. [ARC085D] - NRE
思路分析
将最终的第 \(i\) 对 \(a_i\) 和 \(b_i\) 打包起来，形成 \(i\) 个 01 数对 \((a_i,b_i)\)
令 \(\sum(x,y)\) 表示 \((a_i,b_i)\) 中数对 \((x,y)\) 的个数
你那么所求的答案为：
\]
稍作化简可得：
\text{Answer}
&=\sum(0,1)+\sum(1,0)\\
&=\sum(0,1)+\left[\sum(0,0)+\sum(1,0)\right]-\sum(0,0)
\end{aligned}
\]
发现中括号里的东西等价于 \(b\) 中 \(0\) 的个数，是个定值，所以答案等价于最小化 \(\sum(0,1)-\sum(0,0)\) 的值
考虑 dp，\(dp_i\) 表示前 \(i\) 位 \(\sum(0,1)-\sum(0,0)\) 的最小，边界 \(dp_0=0\)
我们可以直接从 \(dp_{i-1}\) 转移过来，不做修改，\(dp_i\gets\begin{cases}dp_{i-1}+1&b_i=1\\dp_{i-1}-1&b_i=0 \end{cases}\)
如果存在一段可能覆盖成全 \(1\) 的线段 \([l,r]\)，对于 \(r\) 处的 \(dp\) 值，我们有如下的转移方式：
- \([l,r]\) 赋值成 \(1\)，区间 \([l,r]\) 对答案的贡献全部为 \(0\)，\(dp_r\gets dp_{l-1}\)
- 选择区间 \([l,r]\) 并且选择另一个区间 \([l',r']\) 相交并满足 \([l,r]\cup[l',r']=[l',r]\)，此时可以转移：\(dp_r\gets dp_{r'}\)，为了防止区间之间相互覆盖，这里的 \(dp_{r'}\) 获取的值必须是选择 \([l',r']\) 转移而来的
对于这里的第二种转移方法，可以在计算每一个 \(l'\) 的时候覆盖 \([l',r']\) 之后所获取的 \(dp_{r'}\) 的值，查询时查询 \([l-1,r]\) 之间获取的最小值，发现这个操作可以用线段树进行优化，故复杂度 \(\Theta(n\log n)\)
代码呈现
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=2e5+1,INF=1e18;
int n;
namespace solve {
class SegmentTree {
private:
int tree[MAXN<<2];
inline int left(int x) { return x<<1; }
inline int right(int x) { return x<<1|1; }
inline void PushUp(int pos) {
tree[pos]=min(tree[left(pos)],tree[right(pos)]);
return ;
}
public:
inline void Build(int l=1,int r=n,int pos=1) {
if(l==r) {
tree[pos]=INF;
return ;
}
int mid=(l+r)>>1;
Build(l,mid,left(pos));
Build(mid+1,r,right(pos));
PushUp(pos);
return ;
}
inline void Modify(int u,int k,int l=1,int r=n,int pos=1) {
if(l==r) {
tree[pos]=min(tree[pos],k);
return ;
}
int mid=(l+r)>>1;
if(u<=mid) Modify(u,k,l,mid,left(pos));
else Modify(u,k,mid+1,r,right(pos));
PushUp(pos);
return ;
}
inline int Query(int ql,int qr,int l=1,int r=n,int pos=1) {
if(ql<=l&&r<=qr) return tree[pos];
int mid=(l+r)>>1;
if(qr<=mid) return Query(ql,qr,l,mid,left(pos));
if(mid<ql) return Query(ql,qr,mid+1,r,right(pos));
return min(Query(ql,qr,l,mid,left(pos)),Query(ql,qr,mid+1,r,right(pos)));
}
};
}
solve::SegmentTree S;
int dp[MAXN],b[MAXN];
vector <int> sec[MAXN];
signed main() {
int tot=0,m;
scanf("%lld",&n);
for(int i=1;i<=n;++i) {
scanf("%lld",&b[i]);
if(!b[i]) ++tot;
}
scanf("%lld",&m);
for(int i=1;i<=m;++i) {
int l,r;
scanf("%lld%lld",&l,&r);
sec[l].push_back(r);
}
memset(dp,0x3f,sizeof(dp));
dp[0]=0; S.Build();
for(int l=1;l<=n;++l) {
dp[l]=min(dp[l],dp[l-1]+(b[l]==1?1:-1));
for(int r:sec[l]) {
int val=min(dp[l-1],S.Query(max(1ll,l-1),r));
if(val<dp[r]) {
dp[r]=val;
S.Modify(r,val);
}
}
}
printf("%lld\n",dp[n]+tot);
return 0;
}
II. [洛谷2605] - 基站选址
思路分析
设 \(dp_{i,j}\) 表示在前 \(i\) 个村庄中，选择了包括 \(i\) 在内的 \(j\) 个村庄建设基站，那么我们可以得到状态转移方程：
\]
而 \(cost(k,i)\) 表示在第 \(k\) 和第 \(i\) 个村庄建设基站，此时范围在 \([k,i]\) 之间的村庄需要赔偿费的总赔偿款，本题的关键就是快速计算 \(cost(k,i)\)
首先，对于每个村庄 \(i\)，我们可以得到一个范围 \([L_i,R_i]\) 表示如果不想支付这笔赔偿款，那么就要至少在 \([L_i,R_i]\) 中建设一个村庄
因此，对于某个村庄 \(i\)，如果我们已经考虑到 \((R_i,n]\) 中的一个村庄，那么如果我们从 \([1,L_i)\) 处进行转移，那么就需要把 \(cost\) 加上 \(w_i\)
因此，我们可以用一棵线段树维护 \(dp_{k,j-1}+cost(k,i)\)，需要支持区间加，区间查询最小值，然后每次转移完 \(i\) 之后，对于所有 \(R_j=i\) 的 \(j\)，我们将 \([1,L_i)\) 加上 \(w_i\)，为了优化空间复杂度，我们可以只开一棵线段树维护，每次用 \(dp_{1,j}\sim dp_{n,j}\) 进行建树，最终的答案就是每次将所有 \(w_i\) 统计完之后，对整棵线段树的最小值查询算答案即可
时间复杂度 \(\Theta(kn\log n)\)
代码呈现
#include<bits/stdc++.h>
#define int long long
#define pii pair <int,int>
using namespace std;
const int MAXN=2e4+5,INF=1e18;
int n,k,d[MAXN],c[MAXN],s[MAXN],w[MAXN];
int dp[MAXN];
vector <pii> op[MAXN];
class SegmentTree {
private:
struct node {
int min,tag;
} tree[MAXN<<2];
inline int left(int x) {
return x<<1;
}
inline int right(int x) {
return x<<1|1;
}
inline void pushup(int pos) {
tree[pos].min=min(tree[left(pos)].min,tree[right(pos)].min);
}
inline void pushdown(int pos) {
if(!tree[pos].tag) return ;
tree[left(pos)].min+=tree[pos].tag;
tree[left(pos)].tag+=tree[pos].tag;
tree[right(pos)].min+=tree[pos].tag;
tree[right(pos)].tag+=tree[pos].tag;
tree[pos].tag=0;
}
public:
inline void Build(int l=0,int r=n,int pos=1) {
tree[pos].tag=0,tree[pos].min=INF;
if(l==r) {
tree[pos].min=dp[l];
tree[pos].tag=0;
return ;
}
int mid=(l+r)>>1;
Build(l,mid,left(pos));
Build(mid+1,r,right(pos));
pushup(pos);
}
inline void Modify(int ul,int ur,int k,int l=0,int r=n,int pos=1) {
if(ul>ur) return ;
if(ul<=l&&r<=ur) {
tree[pos].min+=k;
tree[pos].tag+=k;
return ;
}
pushdown(pos);
int mid=(l+r)>>1;
if(ul<=mid) Modify(ul,ur,k,l,mid,left(pos));
if(mid<ur) Modify(ul,ur,k,mid+1,r,right(pos));
pushup(pos);
}
inline int Query(int ql,int qr,int l=0,int r=n,int pos=1) {
if(ql>qr) return INF;
if(ql<=l&&r<=qr) return tree[pos].min;
pushdown(pos);
int mid=(l+r)>>1,ret=INF;
if(ql<=mid) ret=min(ret,Query(ql,qr,l,mid,left(pos)));
if(mid<qr) ret=min(ret,Query(ql,qr,mid+1,r,right(pos)));
return ret;
}
} S;
signed main() {
scanf("%lld%lld",&n,&k);
for(int i=2;i<=n;++i) scanf("%lld",&d[i]);
for(int i=1;i<=n;++i) scanf("%lld",&c[i]);
for(int i=1;i<=n;++i) scanf("%lld",&s[i]);
for(int i=1;i<=n;++i) scanf("%lld",&w[i]);
d[0]=-INF,dp[0]=0;
for(int i=1;i<=n;++i) {
int lp=lower_bound(d,d+n+1,d[i]-s[i])-d;
int rp=(upper_bound(d,d+n+1,d[i]+s[i])-d)-1;
op[rp].push_back(make_pair(lp,i));
}
int sum=0;
for(int i=1;i<=n;++i) {
dp[i]=sum+c[i];
for(auto x:op[i]) sum+=w[x.second];
}
int res=dp[n];
for(int t=2;t<=k+1;++t) {
S.Build();
for(int i=1;i<=n;++i) {
dp[i]=S.Query(0,i-1)+c[i];
for(auto x:op[i]) S.Modify(0,x.first-1,w[x.second]);
}
res=min(res,S.Query(0,n));
}
printf("%lld\n",res);
return 0;
}
III. [BZOJ1852] - 最长不下降序列
思路分析
首先，我们考虑对整个序列进行重排，使得：对于 \(i,j\) 如果重排后满足条件必须让 \(i\) 在 \(j\) 的前面，则在序列中 \(i\) 也要在 \(j\) 的前面
如果当且仅当 \(i\) 在 \(j\) 的前面，才满足 \(a_i>b_j\)，那么相反来说有 \(a_j\le b_i\)，因此有 \(a_i+b_i>a_j+b_j\)，所以我们可以对 \(a_i+b_i\) 进行大到小的排序
然后我们就取消掉了重排的限制，可以进行 dp，考虑反向 dp，设 \(dp_{i,j}\) 表示 \([i,n]\) 之间的数，满足 \(b\) 的最大值为 \(j\)，然后可以得到的最多数对数量
此时，我们可以在数对的后面加上 \(i\)，使得 \(b_i\) 成为新的最大值，有：
\]
并且，对于所有 \(j\in(b_i,a_i)\)，我们可以在后面加上第 \(i\) 个，而最大值不受影响：
\]
因此，我们可以维护一棵线段树表示对于当前的 \(i\)，对于每个 \(j\)，维护 \(dp_{i,j}\)
此时，我们的线段树需要区间 \(+1\)，查询区间最大值，单点更新最大值，记得离散化
时间复杂度 \(\Theta(n^2\log n)\)
代码呈现
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+1;
int w;
class SegmentTree {
private:
struct node {
int max,tag;
node() { max=tag=0; }
} tree[MAXN<<3];
inline int left(int x) {
return x<<1;
}
inline int right(int x) {
return x<<1|1;
}
inline void pushup(int pos) {
tree[pos].max=max(tree[left(pos)].max,tree[right(pos)].max);
}
inline void pushdown(int pos) {
if(!tree[pos].tag) return ;
tree[left(pos)].max+=tree[pos].tag;
tree[left(pos)].tag+=tree[pos].tag;
tree[right(pos)].max+=tree[pos].tag;
tree[right(pos)].tag+=tree[pos].tag;
tree[pos].tag=0;
}
public:
inline void Update(int u,int v,int l=1,int r=w,int pos=1) {
if(l==r) {
tree[pos].max=max(tree[pos].max,v);
return ;
}
pushdown(pos);
int mid=(l+r)>>1;
if(u<=mid) Update(u,v,l,mid,left(pos));
else Update(u,v,mid+1,r,right(pos));
pushup(pos);
}
inline void Modify(int ul,int ur,int k,int l=1,int r=w,int pos=1) {
if(ul>ur) return ;
if(ul<=l&&r<=ur) {
tree[pos].max+=k;
tree[pos].tag+=k;
return ;
}
pushdown(pos);
int mid=(l+r)>>1;
if(ul<=mid) Modify(ul,ur,k,l,mid,left(pos));
if(mid<ur) Modify(ul,ur,k,mid+1,r,right(pos));
pushup(pos);
}
inline int Query(int ql,int qr,int l=1,int r=w,int pos=1) {
if(ql>qr) return 0;
if(ql<=l&&r<=qr) return tree[pos].max;
pushdown(pos);
int mid=(l+r)>>1,ret=0;
if(ql<=mid) ret=max(ret,Query(ql,qr,l,mid,left(pos)));
if(mid<qr) ret=max(ret,Query(ql,qr,mid+1,r,right(pos)));
return ret;
}
} S;
struct node {
int A,B;
inline friend bool operator <(const node &x,const node &y) {
return x.A+x.B>y.A+y.B;
}
} p[MAXN];
signed main() {
int n;
vector <int> dsc;
scanf("%d",&n);
for(int i=1;i<=n;++i) {
scanf("%d%d",&p[i].A,&p[i].B);
dsc.push_back(p[i].A);
dsc.push_back(p[i].B);
}
sort(p+1,p+n+1);
sort(dsc.begin(),dsc.end());
dsc.erase(unique(dsc.begin(),dsc.end()),dsc.end());
w=dsc.size();
for(int i=1;i<=n;++i) {
p[i].A=lower_bound(dsc.begin(),dsc.end(),p[i].A)-dsc.begin()+1;
p[i].B=lower_bound(dsc.begin(),dsc.end(),p[i].B)-dsc.begin()+1;
}
for(int i=n;i>=1;--i) {
int v=S.Query(1,min(p[i].B,p[i].A-1))+1;
S.Modify(p[i].B+1,p[i].A-1,1);
S.Update(p[i].B,v);
}
printf("%d\n",S.Query(1,w));
return 0;
}
IV. [CodeForces833B] - The Bakery
思路分析
设 \(dp_{i,j}\) 表示将前 \(i\) 个数分为 \(j\) 段的最大价值，有状态转移方程如下：
\]
其中 \(cost(l,r)\) 表示 \([l,r]\) 中有多少个不同的数
在考虑了某个数 \(a_i\) 之后，考虑上一个出现 \(a_i\) 的位置 \(lst_i\)，显然 \(a_i\) 对之后的数如果从 \((lst_i,i]\) 的区间中转移，有 \(1\) 的贡献，所以线段树维护，支持一下区间加区间查询最大值即可，具体的实现类似第 2 题
时间复杂度 \(\Theta(kn\log n)\)
代码呈现
#include<bits/stdc++.h>
using namespace std;
const int MAXN=35001;
int a[MAXN],lst[MAXN],pos[MAXN],dp[MAXN],n;
class SegmentTree {
private:
struct node {
int max,tag;
node() { max=tag=0; }
} tree[MAXN<<2];
inline int left(int x) {
return x<<1;
}
inline int right(int x) {
return x<<1|1;
}
inline void pushup(int pos) {
tree[pos].max=max(tree[left(pos)].max,tree[right(pos)].max);
}
inline void pushdown(int pos) {
if(!tree[pos].tag) return ;
tree[left(pos)].max+=tree[pos].tag;
tree[left(pos)].tag+=tree[pos].tag;
tree[right(pos)].max+=tree[pos].tag;
tree[right(pos)].tag+=tree[pos].tag;
tree[pos].tag=0;
}
public:
inline void Build(int l=1,int r=n,int pos=1) {
tree[pos].max=tree[pos].tag=0;
if(l==r) {
tree[pos].max=dp[l-1];
return ;
}
int mid=(l+r)>>1;
Build(l,mid,left(pos));
Build(mid+1,r,right(pos));
pushup(pos);
}
inline void Modify(int ul,int ur,int k,int l=1,int r=n,int pos=1) {
if(ul>ur) return ;
if(ul<=l&&r<=ur) {
tree[pos].max+=k;
tree[pos].tag+=k;
return ;
}
pushdown(pos);
int mid=(l+r)>>1;
if(ul<=mid) Modify(ul,ur,k,l,mid,left(pos));
if(mid<ur) Modify(ul,ur,k,mid+1,r,right(pos));
pushup(pos);
}
inline int Query(int ql,int qr,int l=1,int r=n,int pos=1) {
if(ql>qr) return 0;
if(ql<=l&&r<=qr) return tree[pos].max;
pushdown(pos);
int mid=(l+r)>>1,ret=0;
if(ql<=mid) ret=max(ret,Query(ql,qr,l,mid,left(pos)));
if(mid<qr) ret=max(ret,Query(ql,qr,mid+1,r,right(pos)));
return ret;
}
} S;
signed main() {
int k;
scanf("%d%d",&n,&k);
for(int i=1;i<=n;++i) {
scanf("%d",&a[i]);
lst[i]=pos[a[i]]+1;
pos[a[i]]=i;
}
for(int t=1;t<=k;++t) {
S.Build();
for(int i=1;i<=n;++i) {
S.Modify(lst[i],i,1);
dp[i]=S.Query(1,i);
}
}
printf("%d\n",dp[n]);
return 0;
}
另解思路
考虑采用决策单调性优化
感性理解可以得到，假设对于 \(dp_{i,j}\) 和 \(dp_{i',j}\) 其中 \(i>i'\)，分别从 \(dp_{k,j-1}\) 和 \(dp_{k',j-1}\) 处转移得来，应该有：\(k\ge k'\)
这个称为决策单调性，我们可以考虑利用这个性质来优化 dp
我们采用分治的思路，假设对于 \(dp_{l,j}\sim dp_{r,j}\) 中的数，从 \(dp_{L,j-1}\sim dp_{R,j-1}\) 处转移而来
那么我们求出 \(dp_{mid,j}\) 的转移，假设从 \(dp_{M,j-1}\) 处转移，则 \(dp_{l,j}\sim dp_{mid-1,j}\) 应该从 \(dp_{L,j-1}\sim dp_{M,j-1}\) 处转移，而 \(dp_{mid+1}\sim dp_{r,j}\) 要从 \(dp_{M,j-1}\sim dp_{R,j-1}\) 处转移而来
所以原问题就被拆分成两个子问题进一步求解，个人认为这种思路有点像整体二分（？）
至于 \(cost(l,r)\) 的计算，可以类似莫队算法来求解
时间复杂度 \(\Theta(nk\log n)\)
另解代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=35001,MAXK=51;
int a[MAXN],cnt[MAXN],dp[MAXN][MAXK];
int ans,lp=1,rp;
inline void add(int x) {
if(cnt[a[x]]==0) ++ans;
++cnt[a[x]];
}
inline void del(int x) {
--cnt[a[x]];
if(cnt[a[x]]==0) --ans;
}
inline int cost(int l,int r) {
if(lp<l) for(int i=lp;i<l;++i) del(i);
if(lp>l) for(int i=l;i<lp;++i) add(i);
if(rp<r) for(int i=r;i>rp;--i) add(i);
if(rp>r) for(int i=rp;i>r;--i) del(i);
lp=l,rp=r;
return ans;
}
inline void DP(int l,int r,int L,int R,int cur) {
if(l>r) return ;
int mid=(l+r)>>1,M=-1;
for(int i=L;i<=R&&i<=mid;++i) {
int v=dp[i-1][cur-1]+cost(i,mid);
if(v>dp[mid][cur]) dp[mid][cur]=v,M=i;
}
DP(l,mid-1,L,M,cur);
DP(mid+1,r,M,R,cur);
}
signed main() {
int n,k;
scanf("%lld%lld",&n,&k);
for(int i=1;i<=n;++i) scanf("%lld",&a[i]);
memset(dp,-0x3f,sizeof(dp));
dp[0][0]=0;
for(int i=1;i<=k;++i) DP(i,n,i-1,n,i);
printf("%lld\n",dp[n][k]);
return 0;
}
V. [CodeForces868F] - Yet Another Minimization Problem
思路分析
类似上一题的决策单调性，转移方程类似，只需要对 \(cost(l,r)\) 的计算稍作修改即可
代码呈现
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=1e5+1,MAXK=21;
int a[MAXN],cnt[MAXN],dp[MAXN][MAXK];
int ans,lp=1,rp;
inline void add(int x) {
ans+=cnt[a[x]];
++cnt[a[x]];
}
inline void del(int x) {
--cnt[a[x]];
ans-=cnt[a[x]];
}
inline int cost(int l,int r) {
if(lp<l) for(int i=lp;i<l;++i) del(i);
if(lp>l) for(int i=l;i<lp;++i) add(i);
if(rp<r) for(int i=r;i>rp;--i) add(i);
if(rp>r) for(int i=rp;i>r;--i) del(i);
lp=l,rp=r;
return ans;
}
inline void DP(int l,int r,int L,int R,int cur) {
if(l>r) return ;
int mid=(l+r)>>1,M=-1;
for(int i=L;i<=R&&i<=mid;++i) {
int v=dp[i-1][cur-1]+cost(i,mid);
if(v<dp[mid][cur]) dp[mid][cur]=v,M=i;
}
DP(l,mid-1,L,M,cur);
DP(mid+1,r,M,R,cur);
}
signed main() {
int n,k;
scanf("%lld%lld",&n,&k);
for(int i=1;i<=n;++i) scanf("%lld",&a[i]);
memset(dp,0x3f,sizeof(dp));
dp[0][0]=0;
for(int i=1;i<=k;++i) DP(1,n,1,n,i);
printf("%lld\n",dp[n][k]);
return 0;
}
VI. [HDU2829] - Lawrence
思路分析
同样的数列分段问题，设 \(dp_{i,j}\) 表示把前 \(i\) 个数分 \(j\) 段的最小代价，状态转移方程如下：
\]
\(cost(l,r)\) 表示 \(\sum\limits_{i=l}^r\sum\limits_{j=i+1}^r a_i\times a_j\)，即 \([l,r]\) 做一段的代价，通过前缀和计算不难得出 \(cost(l,r)=c_r-c_{l-1}-s_{l-1}\times(s_r-s_{l-1})\)，其中 \(s_i\) 是 \(a_i\) 的前缀和，\(c
_i\) 表示 \(cost(1,i)\)
带入原式并做简单化简，可以发现此题可以用斜率优化，将 \((s_k,dp_{j-1,k}+s_k^2-c_k)\) 看做决策点维护一个下凸壳即可
时间复杂度 \(\Theta(nm)\)
代码呈现
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=1001;
int a[MAXN],s[MAXN],c[MAXN],q[MAXN],dp[2][MAXN],cur;
inline int X(int u) { return s[u]; }
inline int Y(int u) { return dp[cur^1][u]+s[u]*s[u]-c[u]; }
inline double slope(int u,int v) {
return (double)(Y(u)-Y(v))/(double)(X(u)-X(v));
}
signed main() {
while(true) {
int n,m;
scanf("%lld%lld",&n,&m);
if(n==0&&m==0) break;
for(int i=1;i<=n;++i) {
scanf("%lld",&a[i]);
s[i]=s[i-1]+a[i];
c[i]=c[i-1]+a[i]*s[i-1];
dp[1][i]=c[i];
}
int ret=dp[1][n];
for(int k=2;k<=m+1;++k) {
cur=k&1;
int head=1,tail=1;
q[1]=k-1;
for(int i=k;i<=n;++i) {
while(head!=tail&&slope(q[head],q[head+1])<=s[i]) ++head;
int j=q[head]; dp[cur][i]=dp[cur^1][j]+c[i]-c[j]-s[j]*(s[i]-s[j]);
while(head!=tail&&slope(q[tail-1],q[tail])>=slope(q[tail],i)) --tail;
q[++tail]=i;
}
ret=min(ret,dp[cur][n]);
}
printf("%lld\n",ret);
}
return 0;
}
另解思路
同样地，本题也具有决策单调性，也可以使用分治优化 dp
时间复杂度 \(\Theta(mn\log n)\)
另解代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=1005;
int s[MAXN],c[MAXN],a[MAXN],dp[MAXN][MAXN];
inline void DP(int l,int r,int L,int R,int cur) {
if(l>r) return ;
int mid=(l+r)>>1,M=-1;
for(int i=L;i<=R&&i<mid;++i) {
int val=dp[i][cur-1]+c[mid]-c[i]-s[i]*(s[mid]-s[i]);
if(val<dp[mid][cur]) M=i,dp[mid][cur]=val;
}
DP(l,mid-1,L,M,cur);
DP(mid+1,r,M,R,cur);
}
signed main() {
while(true) {
memset(dp,0x3f,sizeof(dp));
int n,m;
scanf("%lld%lld",&n,&m);
if(n==0&&m==0) break;
for(int i=1;i<=n;++i) {
scanf("%lld",&a[i]);
s[i]=s[i-1]+a[i];
c[i]=c[i-1]+a[i]*s[i-1];
dp[i][1]=c[i];
}
int ret=dp[n][1];
for(int i=2;i<=m+1;++i) {
DP(i,n,i-1,n,i);
ret=min(ret,dp[n][i]);
}
printf("%lld\n",ret);
}
return 0;
}
VII. [HDU5791] - ATM Machine
思路分析
人类智慧题启发式 dp
显然，我们先假设 \(dp_{i,j}\) 表示已知钱数不超过 \(i\)，还可以被警告 \(j\) 次时最小的期望次数，状态转移方程如下：
\begin{cases}
0&i=0\\[2ex]
\infty &j=0\\[2ex]
\min\limits_{k=1}^i\left\{\frac k{i+1}\times dp_{k-1,j-1}+\left(1-\frac{k}{i+1}\right)\times dp_{i-k,j}\right\}&\text{otherwise}
\end{cases}
\]
通过人类智慧，我们不难发现，如果 \(w\) 比较大的话，是没什么用的，因为我们可以采用二分的策略，保证花费的次数不超过 \(\left\lfloor\log_2 k\right\rfloor+1\) 次，因此我们的状态设计中 \(j\) 不用太大，只需要 \(\log k\) 级即可
时间复杂度 \(\Theta(k^2\log k)\)
代码呈现
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2001;
const double INF=1e9;
double dp[MAXN][13];
signed main() {
for(int i=1;i<MAXN;++i) {
dp[i][0]=INF;
for(int j=1;j<=12;++j) {
dp[i][j]=INF;
for(int k=1;k<=i;++k) {
dp[i][j]=min(dp[i][j],(double)k/(i+1)*dp[k-1][j-1]+(double)(i+1-k)/(i+1)*dp[i-k][j]+1);
}
}
}
int n,m;
while(scanf("%d%d",&n,&m)!=EOF) {
printf("%.6lf\n",dp[n][min(m,12)]);
}
return 0;
}
VIII. [洛谷1912] - 诗人小 G
思路分析
设 \(dp_i\) 表示划分完前 \(i\) 句诗的最小代价，状态转移方程如下：
\]
其中 \(sum_i\) 是前 \(i\) 首诗的长度和（含空格）
注意到转移具有决策单调性，但是由于这里的转移有顺序关系，即后面的值依赖于前面的值转移，因此我们考虑类似斜率优化 dp 的方法，维护一个单调队列来转移
对于单调队列中的每个元素，我们维护其对应能转移到的区间 \([l,r]\)，其中单调队列中的若干个区间应该是顺序相连的
当每次我们要得到 \(dp_i\) 的值的时候，我们可以把队首所有 \(r<i\) 的节点都丢掉，因为其无法对之后的转移产生贡献
然后我们要插入节点 \(i\)，首先将队尾所有没有 \(i\) 转移优的都丢掉，然后我们就要找到一个位置 \(p\) 使得从 \(p\) 开始，从 \(i\) 转移会比从队尾转移更优，此时 \(i\) 能够转移到的区间就是 \([p,n]\)，显然，通过在区间上二分，我们能够在 \(\Theta(\log n)\) 的时间复杂度内找到 \(p\)，然后压入队尾继续转移即可
注意精度、输出等小细节
时间复杂度 \(\Theta(n\log n)\)
代码呈现
#include<bits/stdc++.h>
#define double long double
using namespace std;
const int MAXN=1e5+1;
struct node {
int l,r,k;
} q[MAXN];
int sum[MAXN],lst[MAXN],nxt[MAXN],stdlen,expo;
char str[MAXN][31];
double dp[MAXN];
inline double ksm(double a,int b=expo) {
double res=1;
while(b) {
if(b&1) res*=a;
a*=a;
b=b>>1;
}
return res;
}
inline double cost(int src,int des) {
return dp[src]+ksm(abs((sum[des]-sum[src]-1)-stdlen));
}
inline void solve() {
int n;
scanf("%d%d%d",&n,&stdlen,&expo);
for(int i=1;i<=n;++i) {
scanf("%s",str[i]+1);
sum[i]=sum[i-1]+strlen(str[i]+1)+1;
}
int head=1,tail=1;
q[1]=(node){1,n,0};
for(int i=1;i<=n;++i) {
while(head!=tail&&q[head].r<i) ++head;
dp[i]=cost(q[head].k,i);
lst[i]=q[head].k;
while(head!=tail&&cost(i,q[tail].l)<=cost(q[tail].k,q[tail].l)) --tail;
int sec=q[tail].r+1,lp=1,rp=n;
while(lp<=rp) {
int mid=(lp+rp)>>1;
if(cost(i,mid)<=cost(q[tail].k,mid)) sec=mid,rp=mid-1;
else lp=mid+1;
}
if(sec>q[tail].l) q[tail].r=sec-1;
else --tail;
if(sec<=n) q[++tail]=(node){sec,n,i};
}
if(dp[n]>1e18) return (void)(puts("Too hard to arrange\n--------------------"));
printf("%.0Lf\n",dp[n]);
for(int i=n;i;i=lst[i]) nxt[lst[i]]=i;
int pos=0;
for(int i=1;i<=n;++i) {
pos=nxt[pos];
for(int j=i;j<pos;++j) printf("%s ",str[j]+1);
printf("%s\n",str[pos]+1);
i=pos;
}
puts("--------------------");
}
signed main() {
int T;
scanf("%d",&T);
while(T--) solve();
return 0;
}
IX. [洛谷3515] - Lightning Conductor
思路分析
将原式的绝对值拆成按 \(j\) 与 \(i\) 的大小关系分割的两段：
\]
显然，里面的第二个式子可以通过对整个序列 reverse 再做一遍第一个式子的求解即可
注意到转移具有决策单调性，直接做即可
时间复杂度 \(\Theta(n\log n)\)
代码呈现
#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e5+1;
const double INF=1e9;
double sqr[MAXN],dp[MAXN];
int a[MAXN];
inline void solve(int l,int r,int L,int R) {
if(l>r) return ;
int mid=(l+r)>>1,M=0;
double val=0;
for(int i=L;i<=mid&&i<=R;++i) {
double w=sqr[mid-i]+a[i]-a[mid];
if(w>val) val=w,M=i;
}
if(val==0) M=mid;
dp[mid]=max(dp[mid],val);
solve(l,mid-1,L,M);
solve(mid+1,r,M,R);
}
signed main() {
int n;
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
for(int i=1;i<=n;++i) sqr[i]=sqrt(i);
solve(1,n,1,n);
reverse(dp+1,dp+n+1);
reverse(a+1,a+n+1);
solve(1,n,1,n);
for(int i=n;i>=1;--i) printf("%d\n",(int)ceil(dp[i]));
return 0;
}
X. [洛谷4072] - 征途
思路分析
终于找到一道决策单调性简单一点的题目啦，来补一发四边形不等式！
显然先简单地推一下式子，有：
\text{Answer}
&=m\sum_{i=1}^mk_i^2-\left(\sum_{i=1}^m k_i\right)^2\\
&=m\sum_{i=1}^mk_i^2-sum_n^2
\end{aligned}
\]
其中 \(sum_i\) 是 \(a_i\) 的前缀和，\(k_i\) 表示每一段的 \(a_i\) 和，因此只需要最小化 \(\sum\limits_{i=1}^m k_i^2\) 即可
设 \(dp_{i,j}\) 表示前 \(i\) 个数分 \(j\) 段的最小代价，状态转移方程如下：
\]
那么这里的转移具有决策单调性，证明如下：
四边形不等式：
对于形如 \(dp_i=\min\{f_j+cost(j,i)\}\) 一类的状态转移方程，如果 \(cost\) 满足以下性质，则 \(dp_i\) 的转移具有决策单调性
\[\forall\ l_1\le l_2\le r_1\le r_2: cost(l_1+r_1)+cost(l_2+r_2)\le cost(l_1,r_2)+cost(l_2,r_1)
\]一般简记为：“相交大于包含”
对于本题的 \(cost(l,r)\) 为 \(\left(\sum\limits_{i=l}^r a_i\right)^2\)，对于上式，我们记：
\[\begin{cases}
w_1&=\sum\limits_{i=l_1}^{l_2} a_i\\[2ex]
w_2&=\sum\limits_{i=l_2}^{r_1} a_i\\[2ex]
w_3&=\sum\limits_{i=r_1}^{r_2} a_i
\end{cases}
\]则带入四边形不等式有：
\[\begin{aligned}
\text{LHS}
&= (w_1+w_2)^2+(w_2+w_3)^2\\
&=w_1^2+2w_2^2+w_3^2+2w_1w_2+2w_2w_3\\
\text{RHS}
&= (w_1+w_2+w_3)^2+w_2^2\\
&= w_1^2+2w_2^2+w_3^2+2w_1w_2+2w_2w_3+2w_3w_1\\
\text{RHS}-\text{LHS}&=2w_1w_3\ge 0\\
\text{RHS}&\ge\text{LHS}
\end{aligned}
\]故得证
分治优化即可
时间复杂度 \(\Theta(mn\log n)\)
代码呈现
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=3001;
int sum[MAXN],dp[MAXN][MAXN];
inline int sqr(int x) { return x*x; }
inline void DP(int l,int r,int L,int R,int cur) {
if(l>r) return ;
int mid=(l+r)>>1,M=-1;
for(int i=L;i<=R&&i<mid;++i) {
int val=dp[i][cur-1]+sqr(sum[mid]-sum[i]);
if(val<dp[mid][cur]) dp[mid][cur]=val,M=i;
}
DP(l,mid-1,L,M,cur);
DP(mid+1,r,M,R,cur);
}
signed main() {
memset(dp,0x3f,sizeof(dp));
int n,m;
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;++i) scanf("%lld",&sum[i]),sum[i]+=sum[i-1];
for(int i=1;i<=n;++i) dp[i][1]=sqr(sum[i]);
for(int i=2;i<=m;++i) DP(i,n,i-1,n,i);
printf("%lld\n",m*dp[n][m]-sqr(sum[n]));
return 0;
}
XI. [BZOJ1767] - harbingers
思路分析
本题并不难，但是细节比较多
首先，我们的状态转移方程很显然，设 \(dp_u\) 为 \(u\to 1\) 的答案，有：
\]
其中 \(dis_v\) 是 \(v\to 1\) 的路径长度
直接斜率优化，把 \((dis_v,dp_v)\) 看做决策点维护下凸壳，每次转移在凸壳上二分斜率 \(\le V_u\) 的临界值即可
注意本题是树上操作，因此我们的单调队列需要支持撤销操作，因此每次删除也要二分找到插入的位置，然后记录下原来队列的状态，回溯之前复原队列即可
时间复杂度 \(\Theta(n\log n)\)
代码呈现
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=1e5+1;
struct node {
int des,val;
};
vector <node> edge[MAXN];
int s[MAXN],w[MAXN],d[MAXN],dp[MAXN];
int q[MAXN],top;
inline double slope(int u,int v) {
return (double)(dp[u]-dp[v])/(double)(d[u]-d[v]);
}
inline int transfer(int u) {
int ret=1,l=2,r=top;
while(l<=r) {
int mid=(l+r)>>1;
if(slope(q[mid],q[mid-1])<=w[u]) ret=mid,l=mid+1;
else r=mid-1;
}
return ret;
}
inline int update(int u) {
int ret=top+1,l=2,r=top;
while(l<=r) {
int mid=(l+r)>>1;
if(slope(q[mid],q[mid-1])>=slope(q[mid],u)) ret=mid,r=mid-1;
else l=mid+1;
}
return ret;
}
inline void dfs(int p,int f) {
int pos=update(p);
int lstpos=pos,lstval=q[pos],lsttop=top;
if(pos) top=pos,q[pos]=p;
for(auto e:edge[p]) {
int v=e.des;
if(v==f) continue;
d[v]=d[p]+e.val;
int k=q[transfer(v)];
dp[v]=dp[k]+(d[v]-d[k])*w[v]+s[v];
dfs(v,p);
}
if(lstpos) q[lstpos]=lstval,top=lsttop;
}
signed main() {
int n;
scanf("%lld",&n);
for(int i=1;i<n;++i) {
int u,v,w;
scanf("%lld%lld%lld",&u,&v,&w);
edge[u].push_back((node){v,w});
edge[v].push_back((node){u,w});
}
for(int i=2;i<=n;++i) scanf("%lld%lld",&s[i],&w[i]);
dfs(1,0);
for(int i=2;i<=n;++i) printf("%lld ",dp[i]);
puts("");
return 0;
}
