线性DP
最长公共子序列
O(n*m)写法
int a[MAXN], b[MAXM], f[MAXN][MAXM];
int dp() {
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if (a[i] == b[j])
f[i][j] = f[i - 1][j - 1] + 1;
else
f[i][j] = std::max(f[i - 1][j], f[i][j - 1]);
return f[n][m];
}
O(nlogn)写法
可以转化为最长上升子序列（LIS）来求，时间复杂度可以优化到nlogn。
#include<bits/stdc++.h>
using namespace std;
int n,i,x,y,j,m,k,f[100005],c[100005],g[100005];
int main()
{
cin>>n;
for (i=1;i<=n;i++)
{
cin>>x;
c[x]=i;
}
for (i=1;i<=n;i++)
{
cin>>y;
f[i]=c[y];
}
memset(g,127,sizeof(g));
g[0]=0;
for (i=1;i<=n;i++)
{
k=lower_bound(g,g+m+1,f[i])-g-1;
if (k==m)
m++;
g[k+1]=min(g[k+1],f[i]);
}
cout<<m<<endl;
}
最长不下降子序列
O(n2)写法
设f[i]表示以i为结尾最长的长度。
int a[MAXN], d[MAXN];
int dp() {
d[1] = 1;
int ans = 1;
for (int i = 2; i <= n; i++) {
d[i] = 1;
for (int j = 1; j < i; j++)
if (a[j] <= a[i]) {
d[i] = max(d[i], d[j] + 1);
ans = max(ans, d[i]);
}
}
return ans;
}
O(nlogn)写法
memset(g,127,sizeof(g));
g[0]=0;
for (i=1;i<=n;i++)
{
k=lower_bound(g,g+m+1,f[i])-g-1;
if (k==m)
m++;
g[k+1]=min(g[k+1],f[i]);
}
cout<<m<<endl;
字符串间的编辑距离
洛谷2758
#include<bits/stdc++.h>
using namespace std;
string a, b; int lena, lenb, i, j, f[2005][2005];
int main()
{
cin >> a >> b;
lena = a.length();
lenb = b.length();
a = '.' + a; b = '.' + b;
for (i = 1; i <= lena; i++)
f[i][0] = i;
for (i = 1; i <= lenb; i++)
f[0][i] = i;
for (i = 1; i <= lena; i++)
for (j = 1; j <= lenb; j++)
if (a[i] == b[j])
f[i][j] = f[i - 1][j - 1];
else
f[i][j] = min({f[i - 1][j], f[i - 1][j - 1], f[i][j - 1]}) + 1;
cout << f[lena][lenb] << '\n';
}
例题
括号序列
第十二届蓝桥杯软件类C/C++大学B组省赛
#define _CRT_SECURE_NO_WARNINGS 1
#include<bits/stdc++.h>
using namespace std;
char s[5005]; long long n, u, v, i, f[5005][5005];
const int mod = 1e9 + 7;
int dp()
{
memset(f, 0, sizeof(f));
f[0][0] = 1;
for (int i = 1; i <= n; i++)
{
if (s[i] == '(')
{
for (int j = 1; j <= n; j++)
f[i][j] = f[i - 1][j - 1];
}
else
{
f[i][0] = (f[i - 1][0] + f[i - 1][1]) % mod;
for (int j = 1; j <= n; j++)
f[i][j] = (f[i - 1][j + 1] + f[i][j - 1]) % mod;
}
}
for (int i = 0; i <= n; i++)
if (f[n][i])
return f[n][i];
return -1;
}
int main()
{
scanf("%s", s + 1);
n = strlen(s + 1);
u = dp();
reverse(s + 1, s + n + 1);
for (i = 1; i <= n; i++)
{
if (s[i] == '(')
s[i] = ')';
else s[i] = '(';
}
v = dp();
cout << (u * v) % mod << '\n';
}
Research Rover
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, m, k, i, j, f[2005][25], b[200005], c[200005], d[200005], s, p, l, q;
const int mod = 1e9 + 7;
struct ff {
int x, y;
}a[2005];
ll poww(ll x, ll y)
{
if (x == 0)
return 1;
ll k = poww(x / 2, y) % mod;
if (x % 2 == 1)
return (k * k % mod) * y % mod;
else return k * k % mod;
}
ll C(ll m, ll n)
{
return (((c[n] * d[n - m]) % mod) * b[m]) % mod;
}
bool cmp(ff t, ff w)
{
if ((t.x < w.x) or (t.x == w.x) and (t.y < w.y))
return 1;
return 0;
}
int main()
{
cin >> n >> m >> k >> p;
for (i = 1; i <= k; i++)
cin >> a[i].x >> a[i].y;
b[0] = 1; c[0] = 1; d[0] = 1;
for (i = 1; i <= 200000; i++)
b[i] = (poww(mod - 2, i) * b[i - 1]) % mod;
for (i = 1; i <= 200000; i++)
{
c[i] = c[i - 1] * i % mod;
d[i] = poww(mod - 2, c[i]) % mod;
}
sort(a, a + k + 1, cmp);
if ((a[k].x != n) or (a[k].y != m))
{
k++; a[k].x = n; a[k].y = m;
}
else p = p - p / 2;
if ((a[1].x == 1) and (a[1].y == 1))
{
for (i = 1; i < k; i++)
{
a[i].x = a[i + 1].x;
a[i].y = a[i + 1].y;
}
k--;
p = p - p / 2;
}
for (i = 1; i <= k; i++)
{
f[i][0] = C(a[i].x - 1, a[i].x - 1 + a[i].y - 1);
for (j = 1; j < i; j++)
if (a[j].y <= a[i].y)
for (l = 1; l <=20; l++)
{
f[i][l] = (f[i][l] + (f[j][l - 1] * C(a[i].x - a[j].x, a[i].x - a[j].x + a[i].y - a[j].y)) % mod) % mod;
f[i][l] = (f[i][l] - (f[j][l] * C(a[i].x - a[j].x, a[i].x - a[j].x + a[i].y - a[j].y)) % mod) % mod;
if (f[i][l] < 0)f[i][l] += mod;
}
}
for (l = 0; l <= 20; l++)
{
q = (q + f[k][l] * p % mod) % mod;
q = (q - f[k][l + 1] * p % mod) % mod;
if (q < 0) q += mod;
p = p - p / 2;
}
s = poww(mod - 2, f[k][0]) * q % mod;
cout << s << '\n';
}