7.6 做题笔记
笔记、梳理、题解合三为一的产物。
P2569 [SCOI2010] 股票交易
考虑 DP，数据允许开到平方级别。
设 $f_{i,j}$ 表示第 $i$ 天持有 $j$ 张股票的最大钱。
四种转移：
-
凭空买入，即本次买入与前面无关。$f_{i,j}=-ap_i\cdot j$。
-
不买不卖，直接从前些天转移。$f_{i,j}=\max{f_{i,j},f_{i-1,j}} $。
-
在前面交易（买或卖）基础上买入，需要满足“两次交易间隔 $w$ 天”的条件。
虽然不一定上一次交易就是第 $i-w-1$ 天，但是由转移 2 得，$f_{i-w-1,k}$ 已经是前面这些天的最优答案，所以可以从这天转移到今天。
注意买入的数量不要超过 $as_i$。方程为：$f_{i,j}=\max{f_{i,j},f_{i-w-1,k}-(j-k)\cdot ap_i}; (j-as_i\leq k<j)$。
-
与转移 3 类似，在前基础上卖出。方程为：$f_{i,j}=\max{f_{i,j},f_{i-w-1,k}+(k-j)\cdot bp_i}; (j<k\leq j+bs_i)$。
发现转移 3，4 均为立方级别时间复杂度。$\max$ 转移可以考虑单调队列优化。
根据乘法分配律，转移 3 方程实际为：$f_{i,j}=\max{f_{i,j},f_{i-w-1,k}+k\cdot ap_i}-j\cdot ap_i$。转移 4 类似，就不写了。区间取最大值的操作，单调队列可完成。
转移时注意顺序与逆序，不要把已更新过的拿来更新其他状态。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
|
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e3+5;
int n,m,w;
int f[N][N];
int q[N],l,r;
int ap,bp,as,bs;
signed main()
{
scanf("%lld%lld%lld",&n,&m,&w);
memset(f,~0x3f,sizeof f);
for(int i=1;i<=n;i++)
{
scanf("%lld%lld%lld%lld",&ap,&bp,&as,&bs);
for(int j=0;j<=as;j++)
f[i][j]=-ap*j;
for(int j=0;j<=m;j++)
f[i][j]=max(f[i][j],f[i-1][j]);
if(i-w-1<0) continue;
l=1,r=0;
for(int j=0;j<=m;j++)
{
while(l<=r&&q[l]<j-as)
l++;
while(l<=r&&f[i-w-1][q[r]]+q[r]*ap<=f[i-w-1][j]+j*ap)
r--;
q[++r]=j;
if(l<=r)
f[i][j]=max(f[i][j],f[i-w-1][q[l]]+q[l]*ap-j*ap);
}
l=1,r=0;
for(int j=m;j>=0;j--)
{
while(l<=r&&q[l]>j+bs)
l++;
while(l<=r&&f[i-w-1][q[r]]+q[r]*bp<=f[i-w-1][j]+j*bp)
r--;
q[++r]=j;
if(l<=r)
f[i][j]=max(f[i][j],f[i-w-1][q[l]]+q[l]*bp-j*bp);
}
}
for(int j=1;j<=m;j++)
f[n][j]=max(f[n][j-1],f[n][j]);
printf("%lld\n",f[n][m]);
return 0;
}
|
「一本通 5.5 例 2」最大连续和
时间只允许线性级别。设 $f_i$ 为以 $i$ 结尾的长度不超过 $m$ 的子串的最大和。
朴素转移：$f_i=\max_j{\sum\limits_{k=j}^i a_k};(j>i-m)$。
预处理前缀和，则 $f_i=\max_j{sum_i-sum_{j-1}};(j>i-m)$。
把 $sum_i$ 提出来，再把 $-sum_{j-1}$ 去负号，$\max$ 也就变成了 $\min$：$f_i=sum_i-\min_j{sum_{j-1}}$。
可以用单调队列解决这个 $\min$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=3e5+5;
int n,m;
int a[N],ans,sum[N];
int q[N],l,r;
signed main()
{
scanf("%lld%lld",&n,&m);
ans=LLONG_MIN;
for(int i=1;i<=n;i++)
scanf("%lld",&a[i]),sum[i]=sum[i-1]+a[i];
l=0,r=0;
for(int i=1;i<=n;i++)
{
while(l<=r&&q[l]<i-m)
l++;
ans=max(ans,sum[i]-sum[q[l]]);
while(l<=r&&sum[q[r]]>=sum[i]) r--;
q[++r]=i;
}
printf("%lld\n",ans);
return 0;
}
|
P3089 [USACO13NOV] Pogo-Cow
时间允许平方级别。设 $f_{i,j}$ 表示当前在 $i$ 点，从 $j$ 点跳来的最大得分。首先按坐标顺序排序。
立方转移：$f_{i,j}=\max{f_{j,k}}+p_i;(x_j-x_k\leq x_i-x_j)$。
这里有一个建立 DP 方程式的 trick：尝试一下把 $f_{i-1,j}$ 带入 $f_{i,j}$。$f_{i,j}=f_{i-1,j}-p_{i-1}+p_i$。
注意这里 $f_{i-1,j}$ 的范围是 $x_{j}-x_k\leq x_{i-1}-x_j$，但是由于 $x_i>x_{i-1}$，所以满足 $f_{i,j}$ 范围的 $k$ 会比满足 $f_{i-1,j}$ 范围的 $k$ 要多。这里简单用 while 拓展一下就好了。
题意是可以一直向左或一直向右，正反做两次 DP 即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
|
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define x first
#define p second
const int N=1e3+5;
int n;
int f[N][N];
pii a[N];
signed main()
{
scanf("%lld",&n);
for(int i=1;i<=n;i++)
scanf("%lld%lld",&a[i].x,&a[i].p);
sort(a+1,a+n+1);
for(int j=1;j<=n;j++)
{
f[j][j]=a[j].p;
for(int i=j+1,k=j+1;i<=n;i++)
{
f[i][j]=f[i-1][j]-a[i-1].p;
while(k-1>=1&&a[j].x-a[k-1].x<=a[i].x-a[j].x)
f[i][j]=max(f[i][j],f[j][--k]);
f[i][j]+=a[i].p;
}
}
for(int j=n;j>=1;j--)
{
f[j][j]=a[j].p;
for(int i=j-1,k=j-1;i>=1;i--)
{
f[i][j]=f[i+1][j]-a[i+1].p;
while(k+1<=n&&a[k+1].x-a[j].x<=a[j].x-a[i].x)
f[i][j]=max(f[i][j],f[j][++k]);
f[i][j]+=a[i].p;
}
}
int ans=LLONG_MIN;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
ans=max(ans,f[i][j]);
printf("%lld\n",ans);
return 0;
}
|
P2627 [USACO11OPEN] Mowing the Lawn G
只允许线性复杂度。设 $f_{i,0/1}$ 表示前 $i$ 头奶牛中 不选/选 这头奶牛。$f_{i,0}=\max{f_{i-1,0},f_{i-1,1}}$，$f_{i,1}=\max_j{f_{j,0}+\sum\limits_{k=j+1}^iE_k};(i-K\leq j< i)$。
预处理前缀和，$f_{i,1}=\max{f_{j,0}+sum_i-sum_{j}}=\max{f_{j,0}-sum_j}+sum_i$。单调队列维护 $\max$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
int n,a[N],sum[N],f[N][2];
int q[N],l,r,k;
signed main()
{
scanf("%lld%lld",&n,&k);
for(int i=1;i<=n;i++)
scanf("%lld",&a[i]),sum[i]=sum[i-1]+a[i];
l=1,r=1;
for(int i=1;i<=n;i++)
{
while(l<=r&&q[l]<i-k) l++;
f[i][0]=max(f[i-1][0],f[i-1][1]);
if(l<=r)
f[i][1]=f[q[l]][0]-sum[q[l]]+sum[i];
while(l<=r&&f[q[r]][0]-sum[q[r]]<f[i][0]-sum[i])
r--;
q[++r]=i;
}
int ans=LLONG_MIN;
for(int i=1;i<=n;i++)
ans=max({ans,f[i][0],f[i][1]});
printf("%lld\n",ans);
return 0;
}
|
P2564 [SCOI2009] 生日礼物
妙妙思路，不知道算不算 DP。
想象一个窗口，当窗口内的种类齐全时，就可以更新答案。窗口的右端点容易推进，直接循环就是了，考虑左端点。可以表示一种彩珠种类最新的位置。这里的最新指窗口右端点左边的最靠近右端点的彩珠。然后，当彩珠左端的位置不再是这个种类的最新位置时，即这个窗口里包含的种类除了它，还有一个也在窗口里，那么我们就可以舍弃掉它、推进左端点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define x first
#define col second
const int N=1e6+5;
int n,m;
pair<int,int> a[N];
int l,tot,k,X[N];
signed main()
{
scanf("%lld%lld",&n,&m);
for(int i=1,t;i<=m;i++)
{
scanf("%lld",&t);
for(int j=1;j<=t;j++)
scanf("%lld",&a[++k].x),a[k].col=i;
}
sort(a+1,a+n+1);
memset(X,-1,sizeof X);
l=1;
int ans=LLONG_MAX;
for(int i=1;i<=n;i++)
{
if(X[a[i].col]==-1)
++tot;
X[a[i].col]=a[i].x;
while(X[a[l].col]!=a[l].x&&l<=n)
l++;
if(tot==m)
ans=min(ans,a[i].x-a[l].x);
}
printf("%lld\n",ans);
return 0;
}
|
POJ 3017 Cut the Sequence
设 $f_i$ 表示前 $i$ 个已被分为若干段的最优答案。$f_i=\min{f_j+\max_{k=j+1}^i a_k};(j<i,\cup sum_i-sum_j\leq m)$。上式可以把 $\max$ 提出来。
对于每个 $i$ 有多个满足条件的 $j$，因为 $f$ 单调不减，所以贡献嘴有答案的是最左边的满足条件的 $j$，记为 $c_i$。可以二分求得 $c_i$。
$\max$ 可以用单调队列搞定。$f_i=f_{c_i}+a_{q_l}$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
int n,m,a[N],c[N],q[N],f[N],sum[N];
signed main()
{
scanf("%lld%lld",&n,&m);
bool flg=1;
for(int i=1;i<=n;i++)
scanf("%lld",&a[i]),sum[i]=sum[i-1]+a[i];
for(int i=1;i<=n;i++)
if(a[i]>m) {flg=0;break;}
if(!flg) return puts("-1"),0;
for(int i=1;i<=n;i++)
{
int l=0,r=i,mid,ans;
while(l<=r)
{
mid=l+r>>1;
if(sum[i]-sum[mid]<=m)
ans=mid,r=mid-1;
else
l=mid+1;
}
c[i]=ans;
}
int l=1,r=0;
for(int i=1;i<=n;i++)
{
while(l<=r&&a[q[r]]<=a[i])
r--;
q[++r]=i;
while(l<=r&&q[l]<=c[i])
l++;
f[i]=f[c[i]]+a[q[l]];
for(int j=l;j<=r;j++)
f[i]=min(f[i],f[q[j]]+a[q[j+1]]);
}
printf("%lld\n",f[n]);
return 0;
}
|
AcWing 298. 围栏
设 $f_{i,j}$ 表示前 $i$ 个工人刷了前 $j$ 个木板的最大价值（可以有一些木板不被刷）。
显然，前一个人可以不刷，或者不刷前一块木板：$f_{i,j}=\max{f_{i-1,j},f_{i,j-1}}$。
朴素转移：$f_{i,j}=\max_{j-l_i\leq k<s_i}{f_{i-1,k}+p_i\cdot(j-k)};(j\geq s_i)$。
把含 $j$ 项提出来，$\max$ 里面就只剩有关 $k$ 项。单调队列优化就搞定了。
实现的时候可以先把符合的 $k$ 塞入单调队列中，然后进行转移求 $f$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
|
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1.6e4+5,M=105;
int n,m;
struct node
{
int l,p,s;
bool operator<(const node &T)const
{
return s<T.s;
}
}a[N];
int f[M][N];
int q[N],l,r;
signed main()
{
scanf("%lld%lld",&n,&m);
for(int i=1;i<=m;i++)
scanf("%lld%lld%lld",&a[i].l,&a[i].p,&a[i].s);
sort(a+1,a+m+1);
for(int i=1;i<=m;i++)
{
l=1,r=0;
for(int k=max(a[i].s-a[i].l,0ll);k<a[i].s;k++)
{
while(l<=r&&f[i-1][q[r]]-a[i].p*q[r]<=f[i-1][k]-a[i].p*k)
--r;
q[++r]=k;
}
for(int j=1;j<=n;j++)
{
f[i][j]=max(f[i-1][j],f[i][j-1]);
if(j>=a[i].s)
{
while(l<=r&&q[l]<j-a[i].l) ++l;
if(l<=r)
f[i][j]=max(f[i][j],a[i].p*j+f[i-1][q[l]]-a[i].p*q[l]);
}
}
}
printf("%lld\n",f[m][n]);
return 0;
}
|
P2254 [NOI2005] 瑰丽华尔兹
设 $f_{i,j}$ 为当前钢琴在 $(i,j)$ 时已滑行的最大距离。
同一时间段内滑动具有唯一性，所以：$f_{i,j}=\max {f_{i-dx,j-dy}+\text{dis}(i,j,i-dx,j-dy)}$。因为滑动只在同一行或列上，所以偏移量可以快速求得，自然想到单调队列优化 DP。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
|
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define val first
#define pos second
const int N=205;
int n,m,sx,sy,K;
int f[N][N],fx[5][2]={0,0,-1,0,1,0,0,-1,0,1};
pair<int,int> q[N];
int l,r,len,ans;
char s[N][N];
bool in(int x,int y)
{
return x>=1&&x<=n&&y>=1&&y<=m;
}
void work(int x,int y,int d)
{
l=1,r=0;
for(int i=1;in(x,y);i++,x+=fx[d][0],y+=fx[d][1])
if(s[x][y]=='x')
l=1,r=0;
else
{
while(l<=r&&q[r].val+i-q[r].pos<f[x][y])
r--;
q[++r]={f[x][y],i};
while(q[r].pos-q[l].pos>len) l++;
f[x][y]=q[l].val+i-q[l].pos;
ans=max(ans,f[x][y]);
}
}
signed main()
{
scanf("%lld%lld%lld%lld%lld",&n,&m,&sx,&sy,&K);
for(int i=1;i<=n;i++)
scanf("%s",s[i]+1);
memset(f,~0x3f,sizeof f);
f[sx][sy]=0;
for(int k=1,s,t,d;k<=K;k++)
{
scanf("%lld%lld%lld",&s,&t,&d);
len=t-s+1;
if(d==1) for(int i=1;i<=m;i++) work(n,i,d);
if(d==2) for(int i=1;i<=m;i++) work(1,i,d);
if(d==3) for(int i=1;i<=n;i++) work(i,m,d);
if(d==4) for(int i=1;i<=n;i++) work(i,1,d);
}
printf("%lld\n",ans);
return 0;
}
|