AcWing 4518. 最低票价

在一个火车旅行很受欢迎的国度，你提前一年计划了一些火车旅行。
在接下来的一年里，你要旅行的日子将以一个名为 days 的数组给出。
每一项是一个从 1 到 365 的整数。
火车票有三种不同的销售方式：

  • 一张为期一天的通行证售价为 costs[0] 美元；
  • 一张为期七天的通行证售价为 costs[1] 美元；
  • 一张为期三十天的通行证售价为 costs[2] 美元。

通行证允许数天无限制的旅行。
例如，如果我们在第 22 天获得一张为期 7 天的通行证，那么我们可以连着旅行 7 天：第 2 天、第 3 天、第 4 天、第 5 天、第 6 天、第 7 天和第 8 天。
返回你想要完成在给定的列表 days中列出的每一天的旅行所需要的最低消费。
输入格式
第一行包含一个整数 n，表示 days 数组的长度。
第二行包含 n 个整数，表示 days[i]。
第三行包含 3 个整数，表示 costs[i]。
输出格式
一个整数，表示旅行所需要的最低消费。
数据范围
1≤n≤365,
1≤days[i]≤365,
daysdays 按顺序严格递增，
1≤costs[i]≤1000。
输入样例：
6
1 4 6 7 8 20 、
2 7 15
输出样例：
11

思路：
考虑状态表示为f[i]：前day[i]天旅行的最低消费
状态转移：f[i] = f[i - 1] + w[1]
f[i] = Math.min(f[i], f[get(i, 7)] + w[2]
f[i] = Math.min(f[i], f[get(i, 30)] + w[3]

  1. import java.util.*;
  3. public class Main {
  4.     static final int N = 400;
  5.     static int[] d = new int[N];
  6.     static int[] f = new int[N];
  7.     static int n;
  8.     static int[] w = new int[4];
  9.     static int[] len = {0, 1, 7, 30};
  10.     public static void main(String[] args) {
  11.         Scanner sc = new Scanner(System.in);
  13.         n = sc.nextInt();
  14.         for (int i = 1; i <= n; i++) {
  15.             d[i] = sc.nextInt();
  16.         }
  17.         for (int i = 1; i <= 3; i++)
  18.             w[i] = sc.nextInt();
  20.         Arrays.fill(f, 0x3f3f3f3f);
  21.         f[0] = 0;
  22.         for (int i = 1; i <= n; i++) {
  23.             for (int j = 1; j <= 3; j++) {
  24.                 f[i] = Math.min(f[i], f[get(i, len[j])] + w[j]);
  25.             }
  26.         }
  27.         System.out.println(f[n]);
  28.     }
  30.     static int get(int i, int x) {
  31.         int t = d[i] - x + 1;
  32.         while (i > 0 && d[i] >= t)
  33.             i--;
  34.         return i;
  35.     }
  36. }

AcWing 4496. 吃水果

n 个小朋友站成一排，等着吃水果。
一共有 m 种水果，每种水果的数量都足够多。
现在，要给每个小朋友都发一个水果，要求：在所有小朋友都拿到水果后，恰好有 k 个小朋友拿到的水果和其左边相邻小朋友拿到的水果不同（最左边的小朋友当然不算数，即最左边的小朋友不包含在 k 个小朋友内）。
请你计算，一共有多少种不同的分发水果的方案。
输入格式
一行，三个整数 n,m,k。
输出格式
一个整数，表示合理的分发水果的方案总数量对 998244353 取模后的结果。
数据范围
前 5 个测试点满足 1≤n,m≤5。
所有测试点满足 1≤n,m≤20001≤n,m≤2000，0≤k≤n−1。
输入样例1：
3 3 0
输出样例1：
3
输入样例2：
3 2 1
输出样例2：
4

思路：
方法1：DP
状态表示：f[i][j]表示前i个小朋友，恰有j个拿到的水果和其左边相邻的小朋友不同的方案数。
初始化：f[1][0] = m
状态转移：
f[i][j] = f[i - 1][j] + (m - 1) * f[i - 1][j - 1]

  1. static final int N = 2010, MOD = 998244353;
  2. static int[][] f = new int[N][N];
  3. static int n, m, k;
  4. static void solve() {
  5.     n = ni();
  6.     m = ni();
  7.     k = ni();
  9.     f[1][0] = m;
  10.     for (int i = 2; i <= n; i++) {
  11.         for (int j = 0; j < i; j++) {
  12.             if (j > 0)
  13.                 f[i][j] = (int)(1L * (m - 1) * f[i - 1][j - 1] % MOD);
  14.             f[i][j] = (f[i][j] + f[i - 1][j]) % MOD;
  15.         }
  16.     }
  17.     out.println(f[n][k]);
  18. }

方法2：数学
先考虑共k + 1个小朋友，除第一个外，每个都与其左边的不同，方案数为线性DP - 图1
然后考虑固定第一个，剩余n - 1个位置如何放置k个小朋友，即线性DP - 图2

  1. static final int N = 2010, MOD = 998244353;
  2. static int[][] f = new int[N][N];
  3. static int n, m, k;
  4. static void solve() {
  5.     n = ni();
  6.     m = ni();
  7.     k = ni();
  8.     if (m == 1) {
  9.         if (k == 0) out.println(1);
  10.         else out.println(0);
  11.         return;
  12.     }
  14.     long s = m;
  15.     for (int i = 1; i <= k; i++)
  16.         s = s * (m - 1) % MOD;
  18.     // c(n - 1, k) * s;
  19.     int res = (int) (1L * fact[n - 1] * infact[k] % MOD * infact[n - 1 - k] % MOD * s % MOD);
  20.     out.println(res);
  22. }
  24. static int[] fact = new int[N], infact = new int[N];
  26. static {
  27.     fact[0] = infact[0] = 1;
  28.     for (int i = 1; i < N; i++) {
  29.         fact[i] = (int) (1L * fact[i - 1] * i % MOD);
  30.         infact[i] = (int) (infact[i - 1] * qmi(i, MOD - 2, MOD) % MOD);
  31.     }
  32. }
  33. static long qmi(long a, long b, long p) {
  34.     long res = 1;
  36.     while (b > 0) {
  37.         if ((b & 1) == 1) {
  38.             res = res * a % p;
  39.         }
  40.         a = a * a % p;
  41.         b >>= 1;
  42.     }
  43.     return res;
  44. }

Acwing 2770. 方格取数

image.png

思路：
第一个难点在于状态定义
f[i][j]表示所有从左上角走到达(i, j)且下一步向右走的路线的集和
属性：最大值
第二个难点在于状态转移的优化
先枚举列，再枚举行
枚举行时需要先从上往下，再从下往上计算两遍才可以遍历所有转移

  1. import java.util.*;
  3. public class Main {
  4.     static final int N = 1010;
  5.     static int[][] a = new int[N][N];
  6.     static long[][] f = new long[N][N];
  7.     static int n, m;
  8.     public static void main(String[] args) {
  9.         Scanner sc = new Scanner(System.in);
  10.         n = sc.nextInt();
  11.         m = sc.nextInt();
  12.         for (int i = 1; i <= n; i++)
  13.             for (int j = 1; j <= m; j++) {
  14.                 a[i][j] = sc.nextInt();
  15.                 f[i][j] = (long)(-1e10);
  16.             }
  18.         int s = 0;
  19.         for (int i = 1; i <= n; i++) {
  20.             s += a[i][1];
  21.             f[i][1] = s;
  22.         }
  24.         for (int j = 2; j <= m; j++) {
  25.             long x = (long)(-1e10);
  26.             for (int i = 1; i <= n; i++) {
  27.                 f[i][j] = Math.max(f[i][j - 1] + a[i][j], x + a[i][j]);
  28.                 x = f[i][j];
  29.             }
  31.             x = (long)(-1e10);
  32.             for (int i = n; i >= 1; i--) {
  33.                 f[i][j] = Math.max(f[i][j], x + a[i][j]);
  34.                 x = Math.max(f[i][j - 1] + a[i][j], x + a[i][j]);
  35.             }
  36.         }
  39.         System.out.println(f[n][m]);
  40.     }
  41. }

京东20220827面试题t3

问长度为n的全由小写字母组成的字符串中，至少含2个"red"子串的方案数。
1 <= n <= 1e6

  1. import java.util.*;
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         Scanner sc = new Scanner(System.in);
  6.         int n = sc.nextInt();
  7.         if (n < 6) {
  8.             System.out.println(0);
  9.             return;
  10.         }
  11.         final int MOD = (int) (1e9 + 7);
  12.         int[] a = new int[n + 1];
  13.         int[][] f = new int[4][4];
  14.         int[][] g = new int[4][4];
  15.         int res = 1;
  16.         for (int i = 0; i < n; i++)
  17.             res = (int) ((res * 26L) % MOD);
  19.         for (int i = 0; i < 4; i++) {
  20.             for (int j = 0; j < 4; j++) {
  21.                 if (i <= 2 && j <= 2)
  22.                     f[i][j] = 1;
  23.                 else if (i == 3 && j == 3)
  24.                     f[i][j] = 23 * 23;
  25.                 else
  26.                     f[i][j] = 23;
  27.             }
  28.         }
  29.         a[0] = 1;
  30.         a[1] = 26;
  31.         a[2] = 26 * 26;
  32.         for (int idx = 3; idx <= n; idx++) {
  33.             for (int k = 0; k < 4; k++) {
  34.                 for (int i = 0; i < 4; i++) {
  35.                     g[k][i] = 0;
  36.                     for (int j = 0; j < 4; j++) {
  37.                         if (k == 3) {
  38.                             g[k][i] = (int) ((g[k][i] + 23L * f[i][j] % MOD) % MOD);
  39.                         } else {
  40.                             if (!(k == 2 && i == 1 && j == 0))
  41.                                 g[k][i] = (g[k][i] + f[i][j]) % MOD;
  42.                         }
  43.                     }
  44.                 }
  45.             }
  46.             int[][] t = f;
  47.             f = g;
  48.             g = t;
  49.             int c = 0;
  50.             for (int i = 0; i < 4; i++)
  51.                 for (int j = 0; j < 4; j++)
  52.                     c = (c + f[i][j]) % MOD;
  53.             a[idx] = c;
  54.         }
  55.         int c = a[n];
  56.         for (int i = 3; i <= n; i++) {
  57.             int pre = i - 3, last = n - i;
  58.             int x = a[pre] == 0 ? MOD : a[pre], y = a[last] == 0 ? MOD : a[last];
  59.             c = (int) ((c + (long) (x) * y % MOD) % MOD);
  60.         }
  61.         System.out.println(((res - c) % MOD + MOD) % MOD);
  62.     }
  63. }