题意
对于两个数列 A和 B，如果它们都包含一段位置不一定连续的数，且数值是严格递增的，那么称这一段数是两个数列的公共上升子序列，而所有的公共上升子序列中最长的就是最长公共上升子序列。
数列 A 和 B的长度均不超过 30003000。
思考
状态表示：f[i][j]代表所有a[1 ~ i]和b[1 ~ j]中以b[j]结尾的公共上升子序列的集合；f[i][j]的值等于该集合的子序列中长度的最大值；
首先依据公共子序列中是否包含a[i]，将f[i][j]所代表的集合划分成两个不重不漏的子集：
不包含a[i]的子集，最大值是f[i - 1][j]；
包含a[i]的子集，将这个子集继续划分，依据是子序列的倒数第二个元素在b[]中是哪个数：
子序列只包含b[j]一个数，长度是1；
子序列的倒数第二个数是b[1]的集合，最大长度是f[i - 1][1] + 1；
…
子序列的倒数第二个数是b[j - 1]的集合，最大长度是f[i - 1][j - 1] + 1；
如果直接按上述思路实现，需要三重循环：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| for (int i = 1; i <= n; i ++ )
{
for (int j = 1; j <= n; j ++ )
{
f[i][j] = f[i - 1][j];
if (a[i] == b[j])
{
int maxv = 1;
for (int k = 1; k < j; k ++ )
if (a[i] > b[k])
maxv = max(maxv, f[i - 1][k] + 1);
f[i][j] = max(f[i][j], maxv);
}
}
}
|
然后我们发现每次循环求得的maxv是满足a[i] > b[k]的f[i - 1][k] + 1的前缀最大值。
因此可以直接将maxv提到第一层循环外面，减少重复计算，此时只剩下两重循环。
最终答案枚举子序列结尾取最大值即可。
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 <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 3010;
int n;
int a[N], b[N];
int f[N][N];
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int j=1;j<=n;j++) cin>>b[j];
a[0]=b[0]=-1;
for(int i=1;i<=n;i++){
int maxv = 1;
for(int j=1;j<=n;j++){
f[i][j] = f[i - 1][j];
if (a[i] == b[j]) f[i][j] = max(f[i][j], maxv);
if (a[i] > b[j]) maxv = max(maxv, f[i - 1][j] + 1);
}
}
int res = 0;
for (int i = 1; i <= n; i ++ ) res = max(res, f[n][i]);
printf("%d\n", res);
return 0;
}
|
技巧总结：在纸上列出式子，考虑怎么用数据结构来优化，这里我们用到的数据结构就是一个int。
题意
给定长度为 $N$ 的序列 $A$, 构造一个长度为 $N$ 的序列 $B$, 满足:
- $B$ 非严格单调, 即 $B_{1} \leq B_{2} \leq \ldots \leq B_{N}$ 或 $B_{1} \geq B_{2} \geq \ldots \geq B_{N}$ 。
- 最小化 $S=\sum_{i=1}^{N}\left|A_{i}-B_{i}\right|_{\text {。 }}$
只需要求出这个最小值 $S_{\text {。 }}$
思考
引理：一定存在一组最小的方案B，B中所有元素都在A中出现过（证明见y总视频）（注意：可以取重复的）
状态表示：f[i][j]表示所有给B[1...i]分配好了值，且最后一个数分配的是A[j]的集合。属性：MIN(S)
状态转移：依据倒数第二个数分配的是哪个A[i]将f[i][j]所代表的集合划分成j个不重不漏的子集：
倒数第二个数选取的是A[1]的所有方案的结合，最小值是f[i - 1][1] + abs(B[i] - A'[j]);
倒数第二个数选取的是A[2]的所有方案的结合，最小值是 f[i - 1][2] + abs(B[i] - A'[j]);
…
f[i][j]在所有子集的最小值中取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
30
31
32
33
34
35
36
37
38
| #include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 2010, INF = 0x3f3f3f3f;
int n;
int a[N], b[N];
int f[N][N];
int dp(){
for(int i=1;i<=n;i++) b[i]=a[i];
sort(b+1,b+1+n);
for(int i=1;i<=n;i++){
int minv=INF;
for(int j=1;j<=n;j++){
minv = min(minv,f[i-1][j]);
f[i][j]=minv+abs(b[j]-a[i]);
}
}
int res=INF;
for(int i=1;i<=n;i++) res=min(res,f[n][i]);
return res;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
int res=dp();
reverse(a+1,a+n+1);
res = min(res,dp());
cout<<res<<endl;
return 0;
}
|
技巧总结：
题意
一个公司有三个移动服务员，最初分别在位置 1，2，3 处.如果某个位置（用一个整数表示）有一个请求，那么公司必须指派某名员工赶到那个地方去。
从 p 到 q 移动一个员工，需要花费 c(p,q)。
公司必须按顺序依次满足所有请求，且过程中不能去其他额外的位置，目标是最小化公司花费，请你帮忙计算这个最小花费。
思考
直接的想法，已完成i-1个请求——>已完成i个请求。f[i][x][y][z]表示已完成i个请求，位置分别是x,y,z。
优化：发现第i个请求完成时，一定会有某个员工在pi上。所以f[i][x][y]
转移：f[i+1,x,y]=min(f[i+1,x,y],f[i,x,y]+c(Pi,Pi+1))
f[i+1,Pi+1,y]=min(f[i+1,Pi,y],f[i,x,y]+c(x,Pi+1))
f[i+1,x,Pi+1]=min(f[i+1,x,Pi+1],f[i,x,y]+c(y,Pi+1))
目标：f[N][?][?]
初始化：P0=3，f[0][1][2]=0
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
| #include<bits/stdc++.h>
using namespace std;
const int N=1010,M=210;
int n,m;
int mp[N][N],p[N];
int f[N][M][M];
int main(){
scanf("%d%d",&m,&n);
for(int i=1;i<=m;i++){
for(int j=1;j<=m;j++){
scanf("%d",&mp[i][j]);
}
}
memset(f,0x3f,sizeof f);
f[0][1][2]=0,p[0]=3;
for(int i=1;i<=n;i++) scanf("%d",&p[i]);
for(int i=0;i<n;i++){
for(int x=1;x<=m;x++){
for(int y=1;y<=m;y++){
int z = p[i], v = f[i][x][y];
if (x == y || x == z || y == z) continue;
int u = p[i + 1];
f[i + 1][x][y] = min(f[i + 1][x][y], v + mp[z][u]);
f[i + 1][z][y] = min(f[i + 1][z][y], v + mp[x][u]);
f[i + 1][x][z] = min(f[i + 1][x][z], v + mp[y][u]);
}
}
}
int res=0x3f3f3f3f;
for(int x=1;x<=m;x++){
for(int y=1;y<=m;y++){
res=min(res,f[n][x][y]);
}
}
cout<<res;
}
|
技巧总结：用尽量少的维度覆盖状态空间。
题意
N*M的矩阵，一开始所有格子都有一个数字，从左上角走到右下角，走2次。经过格子可以拿起格子上的数，每个格子的数只能被拿一次（但可走两次）,求拿起的最大值。
思考
考虑两条路线同时走，状态表示f[X1][Y1][X2][Y2]。
优化：因为X1+Y1=X2+Y2，f[k][X1][X2]，表示第一条从（1，1）—>（x1,k-x1），第二条从（1，1）—>（x2,k-x2）的路线，取得的最大值。
状态划分：找最后一个不同点：最后一步
- 第一条往右，第二条往右
f[k][x1][x2] = f[k-1][x1][x2]+v[x1][k-x1]+(v[x2][k-x2])
- 第一条往右，第二条往下
f[k][x1][x2] = f[k-1][x1][x2-1]+v[x1][k-x1]+(v[x2][k-x2])
- 第一条往下，第二条往右
f[k][x1][x2] = f[k-1][x1-1][x2]+v[x1][k-x1]+(v[x2][k-x2])
- 第一条往下，第二条往下
f[k][x1][x2] = f[k-1][x1-1][x2-1]+v[x1][k-x1]+(v[x2][k-x2])
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
| #include<bits/stdc++.h>
using namespace std;
const int N = 55,M=60;
int n,m;
int w[N][N];
int f[M*2][N][N];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
scanf("%d",&w[i][j]);
}
}
for(int k = 2;k<=n+m;k++){
for(int x1 = max(1,k-m);x1<=min(k-1,n);x1++){
for(int x2 = max(1,k-m);x2<=min(k-1,n);x2++){
int t = w[x1][k-x1];
if(x2!=x1) t+=w[x2][k-x2];
for(int a=0;a<=1;a++){
for(int b=0;b<=1;b++){
f[k][x1][x2] = max(f[k][x1][x2],f[k-1][x1-a][x2-b]+t);
}
}
}
}
}
cout<<f[n+m][n][n];
return 0;
}
|
技巧总结：不要有先走一条路再走第二条的思维定势。
