这是本文档旧的修订版！
动态规划 2
二进制优化
题意
洛谷p1776
给定一个容量为 $m$ 的背包和 $n$ 种物品。每种物品价值为 $v_i$，重量为 $w_i$，数量为 $c_i$。求最多可以得到的价值。
题解
暴力方法为将每种物品转化为 $c_i$ 个独立物品考虑，然后就是一个 $01$ 背包问题。
不难发现任意一个不超过 $c_i$ 的正整数一定用 $1,2,4\cdots 2^n,(c_i-2^{n+1}+1)$ 表示。
于是可以将每种物品拆成 $1,2,4\cdots 2^n,(c_i-2^{n+1}+1)$ 个物品构成的包考虑。
物品总数优化为 $O\left(\sum_{i=1}^n \log {c_i}\right)$，总时间复杂度为 $O\left(m\sum_{i=1}^n \log {c_i}\right)$。
const int MAXM=4e4+5,MAXC=2005;
int dp[MAXM],v[MAXC],w[MAXC];
int main()
{
int n=read_int(),m=read_int(),cnt=0;
_for(i,0,n){
int a=read_int(),b=read_int(),c=read_int();
for(int j=1;j<c;j<<=1){
v[cnt]=j*a,w[cnt++]=j*b;
c-=j;
}
v[cnt]=c*a,w[cnt++]=c*b;
}
_for(i,0,cnt)
for(int j=m;j>=w[i];j--)
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
enter(dp[m]);
return 0;
}
单调队列优化
习题一
题意
一个城镇有 $n$ 个区域，从左到右 $1$ 编号为 $n$，每个区域之间距离 $1$ 个单位距离。
节日中有 $m$ 个烟火要放，给定放的地点 $a_i$，时间 $t_i$。如果你当时在区域 $x$，那么你可以获得 $b_i-\vert a_i-x\vert$ 的开心值。
你每个单位时间可以移动不超过 $d$ 个单位距离。你的初始位置是任意的(初始时刻为 $1$)，求你通过移动能获取到的最大的开心值。
题意
设 $\text{dp}(i,j)$ 表示在 $t_i$ 时刻处于位置 $j$ 能得到的最大快乐值。于是有
$$
\text{dp}(i,j)=\max_{j-d(t_i-t_{i-1})\le k\le j+d(t_i-t_{i-1})}\text{dp}(i-1,k)+b_i-\vert a_i-j\vert
$$
单调队列维护即可。时间复杂度 $O(nm)$。
const int MAXN=15e4+5;
const LL Inf=1e18;
LL dp[2][MAXN];
int que[MAXN];
int main()
{
int n=read_int(),m=read_int(),d=read_int(),pos=0,last=1;
while(m--){
int a=read_int(),b=read_int(),t=read_int()-last;
pos=!pos;
for(int i=1,rpos=1,head=0,tail=1;i<=n;i++){
while(head>=tail&&que[tail]<i-1LL*t*d)tail++;
while(rpos<=n&&rpos<=i+1LL*t*d){
while(head>=tail&&dp[!pos][que[head]]<=dp[!pos][rpos])head--;
que[++head]=rpos++;
}
dp[pos][i]=dp[!pos][que[tail]]+b-abs(a-i);
}
last+=t;
}
LL ans=-Inf;
_rep(i,1,n)
ans=max(ans,dp[pos][i]);
enter(ans);
return 0;
}
习题二
题意
洛谷p1776
给定一个容量为 $m$ 的背包和 $n$ 种物品。每种物品价值为 $v_i$，重量为 $w_i$，数量为 $c_i$。求最多可以得到的价值。
题解
考虑滚动背包，有 $\text{dp}_i=\max_{k\le c}(\text{dp}_{i-kw}+kv)$。设 $i=jw+r$，有
$$
\text{dp}_{jw+r}=\max_{k\le c}(\text{dp}_{jw+r-kw}+kv)=\max_{k\le c}(\text{dp}_{(j-k)w+r}-(j-k)v)+jv
$$
枚举余数 $r$，对每个余数 $r$，维护 $\text{dp}_{aw+r}-av$ 的单调队列即可。时间复杂度 $O(nm)$。
const int MAXM=4e4+5,MAXC=2005;
int dp[MAXM];
pair<int,int> que[MAXM];
int main()
{
int n=read_int(),m=read_int();
_for(i,0,n){
int v=read_int(),w=read_int(),c=read_int();
_for(j,0,w){
if(m<j)continue;
int pos1=(m-j)/w,pos2=pos1,head=0,tail=1;
for(int k=0;pos2>=0&&k<=c;pos2--,k++){
int t=dp[pos2*w+j]-pos2*v;
while(head>=tail&&que[head].second<=t)head--;
que[++head]=make_pair(pos2,t);
}
for(;pos1>=0;pos1--){
while(que[tail].first>pos1)tail++;
dp[pos1*w+j]=max(dp[pos1*w+j],que[tail].second+pos1*v);
if(pos2<0)continue;
int t=dp[pos2*w+j]-pos2*v;
while(head>=tail&&que[head].second<=t)head--;
que[++head]=make_pair(pos2,t);
pos2--;
}
}
}
enter(dp[m]);
return 0;
}
