Easy Part
都是些常见基本模板题
数列长度1＜N＜1000，求给定序列的 数值严格递增的子序列长度；【模板题】
思路 【基于动态规划】
- 状态表示：
dp[i]：以 a[i]结尾的最长上升子序列的长度
- 初始值：
dp[i]=1,i∈[0,n−1] 表示最初一个数本身就是最长上升子序列，长度为 1
- 状态转移：把前
i−1个数字中所有满足条件dp[j]<dp[i]（上升子序列） 的j找出来，那么dp[i]就可以试着更新为以 dp[j] 结尾的最长上升子序列的长度+自己的长度 1，但可能更新后的结果没之前的大，最后两者取max
代码 $O(n^2)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| #include<bits/stdc++.h>
using namespace std;
const int N=1005;
int n,a[N],dp[N];
int main(){
cin>>n;
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
int ans=0;
for(int i=1;i<=n;i++){
dp[i]=1;
for(int j=1;j<i;j++){
if(a[j]<a[i])
dp[i]=max(dp[i],dp[j]+1);
}
ans = max(ans,dp[i]);
}
cout<<ans<<endl;
}
|
AcWing896 最长上升子序列（序列最长100000）
数列长度1＜N＜100 000 ，求数值严格递增的子序列长度
思路【基于二分】
数据达到100000，考虑$nlogn$的算法
代码$O(nlogn)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| #include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N],q[N];
int main(){
ios::sync_with_stdio(false);
int n,cnt=0;
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
q[0]=INT_MIN;
for(int i=1;i<=n;i++){
int l=0,r=cnt;
while(l<r){
int mid=l+r+1>>1;
if(q[mid]<a[i]) l=mid;
else r=mid-1;
}
cnt=max(cnt,r+1);
q[r+1]=a[i];
}
cout<<cnt<<endl;
}
|
更好理解的一种
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| #include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N];
int main(){
int n;cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
vector<int>stk;
stk.push_back(a[0]);
for(int i=1;i<n;i++){
if(a[i]>stk.back()) stk.push_back(a[i]);
else{
int l=0,r=stk.size()-1;
while(l<r){
int mid=l+r>>1;
if(stk[mid]>=a[i]) r=mid;
else l=mid+1;
}
stk[l]=a[i];
}
}
cout<<stk.size()<<endl;
}
|
AcWing897 最长公共子序列
两个长度分别为 N 和 M 的字符串 A 和 B，求既是 A 的子序列又是 B 的子序列的字符串长度最长是多少。
思路
1
2
3
4
5
6
| 状态表示（集合表示）：dp[i][j] 所有在A[1…i]中出现过且在B[1…j]中也出现过的子序列
属性： 最大值
状态计算（集合划分）：根据A[i]是否等于B[j]
1) A[i] == B[j] dp[i][j] → dp[i-1][j-1]+1;
2) A[i] != B[j] dp[i][j] → max(dp[i][j],dp[i-1][j],dp[i][j-1])
|
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| #include<bits/stdc++.h>
using namespace std;
const int N=1010;
char a[N],b[N];
int x,y;
int dp[N][N];
int main(){
ios::sync_with_stdio(false);
cin>>x>>y;
for(int i=1;i<=x;i++) cin>>a[i];
for(int i=1;i<=y;i++) cin>>b[i];
for(int i=1;i<=x;i++){
for(int j=1;j<=y;j++){
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
if(a[i]==b[j])
dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);
}
}
cout<<dp[x][y]<<endl;
}
|
给出 1,2,…n 的两个排列 P1 和 P2 ，求它们的最长公共子序列。n<=100 000
数据范围大，按上一题的思路明显不行，所以考虑：
因为是1到 n的排列，所以两个子序列的元素都相同，只是位置不同
比如
1
2
| P1: 3 1 2 4 5 映射成→ a b c d e 那么
P2: 5 3 1 2 4 映射成→ e a b c d 所以转换成求单个序列的最长上升子序列问题（AcWing896）
|
代码
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
| #include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n;
int a[N],b[N];
int main(){
cin>>n;
for(int i=1;i<=n;i++){
int x;cin>>x;
a[x]=i;
}
for(int i=1;i<=n;i++){
int x;cin>>x;
b[i]=a[x];
}
vector<int>stk;
stk.push_back(b[1]);
for(int i=2;i<=n;i++){
if(stk.back()<b[i]) stk.push_back(b[i]);
else{
*lower_bound(stk.begin(),stk.end(),b[i])=b[i];
}
}
cout<<stk.size()<<endl;
}
|
给两字符串 A 和 B，将 A 经过若干操作变为 B，求出将 A 变为B 至少需要的操作次数。可进行操作有：
- 删除–将字符串 A 中的某个字符删除。
- 插入–在字符串 A 的某个位置插入某个字符。
- 替换–将字符串 A 中的某个字符替换为另一个字符。
思路
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| 状态表示：dp[i][j]: 将A的前i个字符变成B的前j个字符
属性：最小操作次数
状态计算：
1) a[i]==b[j]: → dp[i-1][j-1];
2) 删除：dp[i-1][j]+1;
插入：dp[i][j-1]+1;
替换: dp[i-1][j-1]+1
关于初始化：
1.在for遍历的时候需要用到的但是事先没有的 就要预处理 → 往往就是0、1之类的
2.如果要找min → INF; 要找有负数的max → -INF
因此：
f[0][i]：如果a初始长度是0，只能用插入操作让a变成b
f[i][0]：如果b初始长度是0，只能用删除操作让a变成b
|
代码
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
| #include<bits/stdc++.h>
using namespace std;
const int N=1010;
char a[N],b[N];
int dp[N][N];
int main(){
int n,m;
cin>>n>>a+1;
cin>>m>>b+1;
for(int i=1;i<=n;i++) dp[i][0]=i;
for(int i=1;i<=m;i++) dp[0][i]=i;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i]==b[j]) dp[i][j]=dp[i-1][j-1];
else{
dp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1);
dp[i][j]=min(dp[i-1][j-1]+1,dp[i][j]);
}
}
}
cout<<dp[n][m]<<endl;
}
|
n个长度不超过 10 的字符串以及m 次询问，每次询问给出一个字符串和一个操作次数上限。
对每次询问，求给定的 n 个串中有多少个串可以在上限操作次数内经过操作变成询问给出的字符串。
思路
代码
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<bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m;
char s[N][15];
int dp[15][15];
int dis(char a[],char b[]){
int lena=strlen(a+1);
int lenb=strlen(b+1);
for(int i=0;i<=lena;i++) dp[i][0]=i;
for(int i=0;i<=lenb;i++) dp[0][i]=i;
for(int i=1;i<=lena;i++){
for(int j=1;j<=lenb;j++){
if(a[i]==b[j]) dp[i][j]=dp[i-1][j-1];
else{
dp[i][j]=min(dp[i-1][j],dp[i][j-1])+1;
dp[i][j]=min(dp[i][j],dp[i-1][j-1]+1);
}
}
}
return dp[lena][lenb];
}
int main(){
cin>>n>>m;
for(int i=0;i<n;i++) cin>>(s[i]+1);
while(m--){
char b[15];cin>>(b+1);
int len=0; cin>>len;
int cnt=0;
for(int i=0;i<n;i++){
memset(dp,0,sizeof dp);
if(dis(s[i],b)<=len) cnt++;
}
cout<<cnt<<endl;
}
return 0;
}
|
Medium Part
非模板题目，在基础模板上的一丢丢变化且不难的题
给定序列，求先单调上升再单调下降的最长子序列长度
思路
先分别按数组 顺序和逆序 求以a[i]结尾的最长上升子序列长度f[i]
得到以a[i]结尾的先上升后下降的最长子序列长度即为f[i]+g[i]-1
代码
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
| #include<bits/stdc++.h>
using namespace std;
const int N=1010;
int f[N],g[N],a[N];
int n;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
f[i]=1,g[i]=1;
}
for(int i=1;i<=n;i++){
for(int j=1;j<i;j++){
if(a[i]>a[j]) f[i]=max(f[i],f[j]+1);
}
}
for(int i=n;i>=1;i--){
for(int j=n;j>i;j--){
if(a[i]>a[j]) g[i]=max(g[i],g[j]+1);
}
}
int ans=0;
for(int i=1;i<=n;i++) ans=max(ans,f[i]+g[i]-1);
cout<<ans<<endl;
}
|