最长公共子序列
思路：
O(n^2)的暴力与
- 当ar[i] == br[j]，
O(nlogn)的优化，这个方法只针对于1到n的全排列的时候好用
- 先离散化后，再求LIS
//n2的做法
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
//#pragma GCC optimize("Ofast")
//#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
//#pragma GCC optimize("unroll-loops")
#define eps 1e-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define NMAX 1000 + 50
#define ls p<<1
#define rs p<<1|1
#define mod 1000000007
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define sl(n) scanf("%lld",&n)
#define sll(n,m) scanf("%lld %lld",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define slll(n,m,z) scanf("%lld %lld %lld",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
#define m_p(a,b) make_pair(a, b)
typedef long long ll;
typedef pair <int,int> pii;
typedef unsigned long long ull;
//不开longlong见祖宗!不改范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}
#define MAX 1000000 + 50
int tt;
int n, m, k;
int ar[MAX];
int br[MAX];
map<int, int>mp;
int tot;
int dp[1005][1005];
void work(){
cin>>n;
for(int i = 1; i <= n; ++i)cin>>ar[i];
for(int i = 1; i <= n; ++i)cin>>br[i];
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= n; ++j){
if(ar[i] == br[j])dp[i][j] = max(dp[i - 1][j - 1] + 1, dp[i][j]);
else dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
}
}
cout<<dp[n][n]<<endl;
}
int main(){
io;
// cin>>tt;
// for(int _t = 1; _t <= tt; ++_t){
// printf("Case #%d: ", _t);
work();
// }
return 0;
}
//nlogn的做法
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
//#pragma GCC optimize("Ofast")
//#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
//#pragma GCC optimize("unroll-loops")
#define eps 1e-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define NMAX 1000 + 50
#define ls p<<1
#define rs p<<1|1
#define mod 1000000007
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define sl(n) scanf("%lld",&n)
#define sll(n,m) scanf("%lld %lld",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define slll(n,m,z) scanf("%lld %lld %lld",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
#define m_p(a,b) make_pair(a, b)
typedef long long ll;
typedef pair <int,int> pii;
typedef unsigned long long ull;
//不开longlong见祖宗!不改范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}
#define MAX 1000000 + 50
int tt;
int n, m, k;
int ar[MAX];
int br[MAX];
map<int, int>mp;
int tot;
int dp[MAX];
void work(){
cin>>n;
for(int i = 1; i <= n; ++i){
cin>>ar[i];
mp[ar[i]] = i;
}
for(int i = 1; i <= n; ++i){
cin>>k;
br[i] = mp[k];
}
dp[++tot] = br[1];
for(int i = 2; i <= n; ++i){
if(dp[tot] < br[i])dp[++tot] = br[i];
else {
ll pos = lower_bound(dp + 1, dp + 1 + tot, br[i]) - dp;
dp[pos] = br[i];
}
}
cout<<tot<<endl;
}
int main(){
io;
// cin>>tt;
// for(int _t = 1; _t <= tt; ++_t){
// printf("Case #%d: ", _t);
work();
// }
return 0;
}
[HAOI2010]最长公共子序列
题目描述：
求最长公共子序列的长度与数量，并对1e8取模
思路：
先看看最长公共子序列的长度
- 当ar[i] = br[j]时，dp[i] [j] = dp[i – 1] [j – 1] + 1
- dp[i] [j] = max(dp[i – 1] [j], dp[i] [j – 1])
那根据这个方法我们考虑第二问
状态：num[i] [j] 表示a串的前 i 个，b串的前j个的最长公共子序列的数量
- 当ar[i] = br[j] 时，num[i] [j] = num[i – 1] [j – 1]，这是因为产生了更长的公共子序列，所以说num在原来的基础上加1
- 如果dp[i] [j] = dp[i – 1] [j]，num[i] [j] += num[i – 1] [j] ，这就说明(i, j)可以从(i – 1, j)转移而来，因为他们的最长公共子序列的长度相同，那就可以加上他的数量
- 同样的，如果dp[i] [j] = dp[i] [j – 1]，num[i] [j] += num[i] [j – 1]
- 最后，如果dp[i] [j] = dp[i – 1] [j – 1]，num[i] [j] -= num[i – 1] [j – 1]，这是因为此时dp[i – 1] [j] = dp[i] [j – 1] = dp[i – 1] [j – 1]，(i-1, j)和(i, j – 1)的状态都由(i – 1, j – 1)转移而来，也就是说其实(i-1, j)和(i, j – 1)的数量就是(i – 1, j – 1)的 ，此时上面的二三条都会加上，这样就相当于加了两次(i – 1, j – 1) ,那我们减去一次就行
换种方法理解：
求最短路长度+最短路计数
我们抽象成n * m的一个图，如果ai = bj那我们就可以从(i – 1, j – 1)向(i, j)连一条边，这条边就是捷径，那我们要求最长公共子序列，其实就可以转换成从(1, 1)到(n , m)的最短路，或者说是找捷径数量最多的路！
那第二问就变成了找捷径数量最多的不同的路径数量，显然，如果ar[i] = br[j],那 (i, j)可以由(i – 1, j – 1)转移而来，也就是num[i] [j] = num[i – 1] [j – 1] + 1，当然也可以不走捷径，从(i – 1, j)或者(i, j – 1)走来，但能更新num的前提是和(i, j)的dp值相同，因为dp相同才代表当前的最大的捷径数相同，说明我们可以加上他们的方案数，但是如果dp[i – 1] [j – 1] = d[i] [j]，就说明从(i – 1, j – 1)到(i, j)并没有经过新的捷径，那(i – 1, j)和(i, j – 1)也是从(i – 1, j – 1)而来，转移到(i, j)就会导致加了两遍相同的路径数量，这是会影响答案的，我们就得剪掉
还有一个问题就是，在牛客上如果开n * m的int数组不会炸，但放洛谷上就会炸，所以我们得会压缩空间，因为每一次都只和上一行的有关，所以我们只需要在第一维保留两个空间即可，用异或来实现滚动的操作
/*
Work by: Chelsea
Problem: 不知名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
//#pragma GCC optimize("Ofast")
//#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
//#pragma GCC optimize("unroll-loops")
#define eps 1e-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define NMAX 1000 + 50
#define ls p<<1
#define rs p<<1|1
#define mod 100000000
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define sl(n) scanf("%lld",&n)
#define sll(n,m) scanf("%lld %lld",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define slll(n,m,z) scanf("%lld %lld %lld",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
#define m_p(a,b) make_pair(a, b)
typedef long long ll;
typedef pair <int,int> pii;
typedef unsigned long long ull;
//不开longlong见祖宗!不改范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}
#define MAX 1000000 + 50
int tt;
int n, m, k;
int dp[5005][5005];
int num[5005][5005];
string ar, br;
void work(){
cin>>ar>>br;
n = (int)ar.size() - 1;
m = (int)br.size() - 1;
ar = " " + ar;
br = " " + br;
for(int i = 0; i <= n; ++i)num[i][0] = 1;
for(int i = 0; i <= m; ++i)num[0][i] = 1;
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= m; ++j){
if(ar[i] == br[j])
{
dp[i][j] = max(dp[i - 1][j - 1] + 1, dp[i][j]);
num[i][j] = num[i - 1][j - 1];
}
else dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
if(dp[i][j] == dp[i - 1][j - 1])num[i][j] -= num[i - 1][j - 1];
if(dp[i][j] == dp[i - 1][j])num[i][j] += num[i - 1][j];
if(dp[i][j] == dp[i][j - 1])num[i][j] += num[i][j - 1];
num[i][j] = (num[i][j] + mod) % mod;
}
}
cout<<dp[n][m]<<endl<<num[n][m]<<endl;
}
int main(){
io;
// cin>>tt;
// for(int _t = 1; _t <= tt; ++_t){
// printf("Case #%d: ", _t);
work();
// }
return 0;
}
/*
Work by: Chelsea
Problem: 不知名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
//#pragma GCC optimize("Ofast")
//#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
//#pragma GCC optimize("unroll-loops")
#define eps 1e-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define NMAX 1000 + 50
#define ls p<<1
#define rs p<<1|1
#define mod 100000000
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define sl(n) scanf("%lld",&n)
#define sll(n,m) scanf("%lld %lld",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define slll(n,m,z) scanf("%lld %lld %lld",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
#define m_p(a,b) make_pair(a, b)
typedef long long ll;
typedef pair <int,int> pii;
typedef unsigned long long ull;
//不开longlong见祖宗!不改范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}
#define MAX 1000000 + 50
int tt;
int n, m, k;
int dp[2][5005];
int num[2][5005];
string ar, br;
void work(){
cin>>ar>>br;
n = (int)ar.size() - 1;
m = (int)br.size() - 1;
ar = " " + ar;
br = " " + br;
for(int i = 0; i <= m; ++i)num[0][i] = 1;
num[1][0] = 1;
for(int i = 1; i <= n; ++i){
int p = i % 2;
for(int j = 1; j <= m; ++j){
num[p][j] = 0;//这里很重要，要清零，也可以写个for放外面清零
if(ar[i] == br[j])
{
dp[p][j] = max(dp[p ^ 1][j - 1] + 1, dp[p][j]);
num[p][j] = num[p ^ 1][j - 1];
}
else dp[p][j] = max(dp[p][j - 1], dp[p^1][j]);
if(dp[p][j] == dp[p^1][j - 1])num[p][j] -= num[p^1][j - 1];
if(dp[p][j] == dp[p^1][j])num[p][j] += num[p^1][j];
if(dp[p][j] == dp[p][j - 1])num[p][j] += num[p][j - 1];
num[p][j] = (num[p][j] + mod) % mod;
}
}
cout<<dp[n % 2][m]<<endl<<num[n % 2][m]<<endl;
}
int main(){
io;
// cin>>tt;
// for(int _t = 1; _t <= tt; ++_t){
// printf("Case #%d: ", _t);
work();
// }
return 0;
}
