1049. 大盗阿福

这道题其实就是 LeetCode 打家劫舍。可以用状态机的方式来思考。

大盗阿福 状态机 DP 分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
using namespace std;

const int N = 1e5 + 10, INF = 0x3f3f3f3f;
int f[N][2];
int w[N];

int main() {
  int T;
  cin >> T;
  while (T--) {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> w[i];
    f[0][0] = 0, f[0][1] = -INF;
    for (int i = 1; i <= n; i++) {
      f[i][0] = max(f[i - 1][0], f[i - 1][1]);
      f[i][1] = f[i - 1][0] + w[i];
    }
    cout << max(f[n][0], f[n][1]) << endl;
  }
  return 0;
}

1057. 股票买卖 IV

用状态机来表示一次交易。

股票交易状态机

f(i,j,0)f(i,j,0) 表示前 i 天，完成的完整交易数为 j，且手中无货的方案
f(i,j,1)f(i,j,1) 表示前 i 天，完成的完整交易数为 j，且手中有货的方案

手中无货的状态可能从两种状态转移过来：

  1. 之前手里无货，当前这笔交易也没买；
  2. 之前手里有货然后卖了。

可以得到转移方程：

f(i,j,0)=max(f(i−1,j,0),f(i−1,j,1)+wi)f(i,j,0)=max(f(i-1,j,0),f(i-1,j,1)+w_i)

手中有货的状态可能从两种状态转移过来：

  1. 之前手里有货，当前这笔交易也没卖出；
  2. 之前手里没货然后当前这笔交易买了。

可以得到转移方程：

f(i,j,1)=max(f(i−1,j,1),f(i−1,j−1,0)−wi)f(i,j,1)=max(f(i-1,j,1),f(i-1,j-1,0)-w_i)

卖出行为会构成一次完整的交易，所以进行该类转移时， j 的参数也要变动。

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 <cstring>
#include <iostream>
using namespace std;

const int N = 100010, M = 110, INF = 0x3f3f3f3f;

int n, m;
int w[N];
int f[N][M][2];

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) scanf("%d", &w[i]);
  memset(f, -0x3f, sizeof f);
  for (int i = 0; i <= n; i++) f[i][0][0] = 0;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      f[i][j][0] = max(f[i - 1][j][0], f[i - 1][j][1] + w[i]);
      f[i][j][1] = max(f[i - 1][j][1], f[i - 1][j - 1][0] - w[i]);
    }
  }
  int res = 0;
  for (int i = 0; i <= m; i++) res = max(res, f[n][i][0]);
  printf("%d\n", res);
  return 0;
}

1058. 股票买卖 V

这道题在卖出股票后有 1 天冷冻期，在考虑状态机的时候，我们定义三个状态：

  1. 手中有货
  2. 手中无货第 1 天，处于冷冻期
  3. 手中无货 >= 2 天，可以交易

状态转移如图所示：

股票交易状态机

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
using namespace std;

const int N = 1e5 + 10, INF = 0x3f3f3f3f;
int w[N];
int f[N][3];
int n;

int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &w[i]);
  f[0][2] = 0;
  f[0][1] = f[0][0] = -INF;
  for (int i = 1; i <= n; i++) {
    f[i][0] = max(f[i - 1][0], f[i - 1][2] - w[i]);
    f[i][1] = f[i - 1][0] + w[i];
    f[i][2] = max(f[i - 1][1], f[i - 1][2]);
  }
  printf("%d\n", max(f[n][1], f[n][2]));
  return 0;
}

1052. 设计密码

f[i][j] 状态表示当前密码已经生成了 i 位，且第 i 位匹配在子串中的位置为 j 的方案数。

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 <cstring>
#include <iostream>
using namespace std;

const int N = 55, mod = 1e9 + 7;
int n, m;
char str[N];
int f[N][N];

int main() {
  cin >> n >> str + 1;
  m = strlen(str + 1);

  // KMP 求模板串的 next 数组
  int ne[N] = {0};
  for (int i = 2, j = 0; i <= n; i++) {
    while (j && str[i] != str[j + 1]) j = ne[j];
    if (str[i] == str[j + 1]) j++;
    ne[i] = j;
  }
  // 当前密码已经生成了 0 位，且第 0 位匹配在子串中的位置为 0 的方案数，初始状态为 1
  f[0][0] = 1;
  // 枚举生成的密码的位置
  for (int i = 0; i < n; i++) {
    // 枚举 KMP 匹配到的子串中的位置，由于题目要求密码中不能包含子串，所以不能有 m
    for (int j = 0; j < m; j++) {
      // 枚举当前位置可以生成的字符的所有可能 a~z
      for (char k = 'a'; k <= 'z'; k++) {
        int u = j;
        while (u && k != str[u + 1]) u = ne[u];
        if (k == str[u + 1]) u++;
        if (u < m) {
          f[i + 1][u] = (f[i + 1][u] + f[i][j]) % mod;
        }
      }
    }
  }
  int res = 0;
  for (int i = 0; i < m; i++) res = (res + f[n][i]) % mod;
  cout << res << endl;
  return 0;
}

这道题没太 get 到精髓，先记录。