CF 358D Dima and Hares

N个物品排成一排,按照一定顺序将所有物品都拿走，如果拿走某个物品时相邻两个物品都没有被拿过，那么得到的价值为ai；如果相邻的两个物品有一个被拿过（左右无所谓），那么得到的价值为bi；如果相邻的两个物品都被拿走了，那么对应价值为ci。问能够获得的最高价值为多少。

题解

CF 683 B. Catching Cheaters

背景：最长公共子序列（LCS） https://leetcode-cn.com/problems/longest-common-subsequence/

给你 n,m(<=5000)，长为 n 的字符串 s，长为 m 的字符串 t。定义 LCS(x,y) 表示字符串 x 和 y 的最长公共子序列。

请你选择 s 的子串 s’，t 的子串 t’，最大化 4*len(LCS(s’,t’))-len(s’)-len(t’) 的值。
输出这个最大值。

输入的字符串只包含小写字母。

子串是连续的，子序列不要求连续。

思路：
LCS的变种
设x = len(lcs(s', t')), a = len(s'), b = len(t')
即max(x - (a - x) + x - (b - x)
对于一段s' t'来讲，属于lcs部分的贡献为2，否则贡献为-1
故在原LCS的基础上做修改即可

  1. static String s, t;
  2. static void solve() {
  3.     int n = ni(), m = ni();
  4.     s = ns();
  5.     t = ns();
  6.     int[][] f = new int[n + 1][m + 1];
  8.     int ans = 0;
  9.     for (int i = 1; i <= n; i++) {
  10.         for (int j = 1; j <= m; j++) {
  11.             f[i][j] = Math.max(0, Math.max(f[i - 1][j] - 1, f[i][j - 1] - 1));
  12.             if (s.charAt(i - 1) == t.charAt(j - 1))
  13.                 f[i][j] = Math.max(f[i][j], f[i - 1][j - 1] + 2);
  14.             ans = Math.max(ans, f[i][j]);
  15.         }
  16.     }
  18.     out.println(ans);
  19. }

CF Educational 57 D. Easy Problem

给你一个 n(<=1e5)，一个长为 n 的字符串 s 和一个长为 n 的数组 a(1<=a[i]<=998244353)。
表示每个 s[i] 都有一个对应的删除代价 a[i]。

请你删除 s 中的某些字符，使得 s 不包含 “hard” 子序列。
输出被删除字母的代价之和的最小值。

子序列不要求连续。s 仅包含小写字母。

思路：
DP，难点在于如何进行状态表示
首先考虑单个字符的情况，再依次考虑多个字符的情况
若题意为”请你删除 s 中的某些字符，使得 s 不包含 “h” 子序列”，删除所有的'h'即可
若题意为”请你删除 s 中的某些字符，使得 s 不包含 “ha” 子序列”，考虑当前字符如果是'a'，需保证要么前面没有'h'出现，要么删除当前'a'
…
故可考虑状态表示为f[i][j]表示考虑前i个字符，不包含"hard"[:j)子序列的所有删除方案。
属性是最小删除代价

状态转移：
s[i] == c[j], f[i][j] = min(f[i - 1][j - 1], f[i - 1][j] + a[i]
s[i] != c[j], f[i][j] = f[i - 1][j]

  1. static final int N = 100010;
  2.     static String s;
  3.     static int[] a = new int[N];
  4.     static int n;
  5.     static long[][] f = new long[N][5];
  6.     static void solve() {
  7.         n = ni();
  8.         s = " " + ns();
  9.         for (int i = 1; i <= n; i++)
  10.             a[i] = ni();
  12.         char[] ch = {' ', 'h', 'a', 'r', 'd'};
  13.         for (int i = 0; i <= n; i++)
  14.             f[i][0] = (long)(1e18);
  16.         for (int i = 1; i <= n; i++) {
  17.             char c = s.charAt(i);
  18.             for (int j = 1; j <= 4; j++) {
  19.                 if (c != ch[j])
  20.                     f[i][j] = f[i - 1][j];
  21.                 else
  22.                     f[i][j] = Math.min(f[i - 1][j - 1], f[i - 1][j] + a[i]);
  23.             }
  24.         }
  26.         out.println(f[n][4]);
  27.     }

CF 1716 D. Chip Move

给定n和k，初始位于0处，第一次移动步长为k的整数倍，第x次移动步长为k + x - 1的整数倍
不限移动次数，问从0移动到[1, n]的方案数各为多少？
数据范围：
n, k ∈ [1, 200000]

思路：
DP
极限情况n = 20000, k = 1
从0开始，最多不超过700步可达n。
故可使用滚动数组，考虑每一步的情况，再利用前缀和加速计算
tmp[i]表示当前步数情况下到i的方案数
pre[i]表示上一轮到i的方案数
res[i]记录最终结果

  1. static final int N = 200010, MOD = 998244353, M = 700;
  2. static int[] tmp = new int[N], pre = new int[N], res = new int[N];
  3. static int n, k;
  4. static void solve() {
  5.     n = ni();
  6.     k = ni();
  8.     // 一开始位于0处，方案数为1
  9.     pre[0] = 1;
  11.     // 模拟每一轮
  12.     for (int t = k, c = 1; t <= n && c <= M; t++, c++) {
  13.         // 枚举可能的起点
  14.         for (int st = 0; st < t; st++) {
  15.             // 前缀和加速计算
  16.             int s = 0;
  17.             for (int i = st; i <= n; i += t) {
  18.                 // 计算当前轮
  19.                 tmp[i] += s;
  20.                 if (tmp[i] >= MOD) tmp[i] -= MOD;
  21.                 // 累计方案数
  22.                 s += pre[i];
  23.                 if (s >= MOD) s -= MOD;
  24.             }
  25.         }
  27.         boolean flag = false;
  28.         for (int i = 0; i <= n; i++) {
  29.             pre[i] = tmp[i];
  30.             res[i] += tmp[i];
  31.             if (res[i] >= MOD) res[i] -= MOD;
  32.             tmp[i] = 0;
  33.             if (pre[i] > 0) flag = true;
  34.         }
  35.         if (!flag) break;
  36.     }
  38.     for (int i = 1; i <= n; i++)
  39.         out.print(res[i] + " ");
  40. }