openjudge动态规划

感觉之前使用md的姿势好像不对 = =

ref: https://fancypei.github.io/OpenjudgeDP/

LCIS $$O(n^2)$$

dp[i][j] 表示a串前i个和以b[j]结尾的串的LCIS的长度

转移是:

dp[i][j]=max(dp[i][j],dp[i-1][k]+1) a[i]==b[j]&&b[k]<b[j] 1<=k<j

dp[i][j]=max(dp[i][j],dp[i-1][j]) a[i]!=b[j]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
for (i = 1; i <= m; i++) {
for (j = 1; j <= n; j++) {
dp[i][j] = 0;
if (x[i] != y[j]) {
dp[i][j] = dp[i - 1][j];
} else {
for (k = 1; k < j; ++k) {
if (dp[i][j] < dp[i - 1][k] && y[k] < y[j]) {
dp[i][j] = dp[i - 1][k];
}
}
dp[i][j] += 1;
}
}
}

第二个式子i从i-1转移过来,所以可以把i放到外层。这样内层循环的时候a[i]是固定的。根据第一个式子,a[i] == b[j] > b[k],实际上要找的是b[j] < a[i] 的最大的dp[i - 1][j],在内层循环的同时存一下就好了,不需要再去枚举那个k了。所以平方的复杂度就能做了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
for (i = 1; i <= m; i++) {
mlen = 0;
for (j = 1; j <= n; j++) {
dp[i][j] = dp[i - 1][j];
//更新mlen
if (y[j] < x[i] && dp[i - 1][j] > mlen) {
mlen = dp[i - 1][j];
}
//计算dp[i][j]
if (y[j] == x[i]) {
dp[i][j] = mlen + 1;
}
}
}

https://github.com/Ir1d/Fantasy/blob/master/POJ/2127.cpp

(openjudge没有spj)

记录路径的姿势都忘光了= =

1
2
3
4
5
6
7
x = n; p = 0;
while (ans--) {
st[++p] = b[y];
while (a[x] != b[y]) --x;
y = pre[x][y];
--x;
}

ref: http://blog.fly2best.com/algorithm/2013/05/11/longges-common-increasing-subsequence/

四边形不等式

  • 7627 鸡蛋的硬度

f[i][j]=min(1+max(f[i-1][t-1],f[i][j-t])

1
2
3
4
5
6
7
for (int i = 1; i <= 100; i++) f[1][i] = i;
for (int i = 2; i <= 10; i++)
for (int j = 1; j <= 100; j++) {
f[i][j] = 1 + max(f[i - 1][0], f[i][j - 1]);
for (int t = 2; t <= j; t++)
f[i][j] = min(f[i][j], 1 + max(f[i - 1][t - 1], f[i][j - t]));
}
  • 9265:取数游戏

    自然数1到N,按顺序列成一排,你可以从中取走任意个数,但是相邻的两个不可以同时被取走.

    答案是斐波那契数,考虑最后一个取(dp[i - 2]),或者不取(dp[i - 1]).

  • 9267:核电站

    加强,变成不能连续m个

    1
    2
    3
    4
    5
    g(i, 0, m) dp[i] = 1LL << i;
    --dp[m];
    g(i, m + 1, n) {
    dp[i] = 2 * dp[i - 1] - dp[i - m - 1];
    }
  • 9268:酒鬼

    不能连续取三个,问取出的最大权值和

1
2
3
4
5
6
// f是最远,g是到i结束
// 答案是f[n]
for (i = 3; i <= n; i++) {
g[i] = v[i] + max(f[i - 2], v[i - 1] + f[i - 3]);
f[i] = max(g[i], f[i - 1]);
}

dp[i][j]表示前i个集合取j个数的种类数

然后 $$dp[i][j] = \sum_{k=0}^{min(cnt_i, j)} dp[i - 1][j - k]$$