Codeforces Round 863 (Div. 3) G2. Vlad and the Nice Paths (hard version)

题意：

给定一个长度为$n$的序列和整数$k$，每个序列颜色为$a[i]$，找出一个子序列的长度为$k$的倍数，假设为$len$，则将这个子序列分为$len/k$份，每份的颜色都相同。求长度最长的这样的子序列的个数。

解法1：

定义 d p [ i ] = { 以 i 颜色结尾的最大长度，数量 } dp[i]=\\{ 以i颜色结尾的最大长度，数量\\} dp[i]={以i颜色结尾的最大长度，数量}
转移的话也较容易转移。

signed main() {
#ifdef JANGYIfreopen("input.in", "r", stdin);freopen("out.out", "w", stdout);
#endifios::sync_with_stdio(false);cin.tie(0); cout.tie(0);init();int T;cin >> T;while(T--) {int n, k; cin >> n >> k;vector<int> a(n + 1);for(int i = 1; i <= n; i++) cin >> a[i];vector<vector<int>> sum(n + 1, vector<int> (n + 1));for(int i = 1; i <= n; i++) {for(int j = 1; j <= n; j++) {sum[i][j] = sum[i][j - 1] + (a[j] == i);}}vector<pair<int, mint>> dp(n + 1);dp[0] = {0, 1};int mx = 0;for(int i = 1; i <= n; i++) {for(int j = 0; j < i; j++) {int cnt = sum[a[i]][i] - sum[a[i]][j];if(cnt >= k) {if(dp[j].fi + k > dp[i].fi) {dp[i] = {dp[j].fi + k, dp[j].se * C(cnt - 1, k - 1)};} else if(dp[j].fi + k == dp[i].fi) {dp[i].se += dp[j].se * C(cnt - 1, k - 1);}mx = max(mx, dp[i].fi);}}}mint ans;for(int i = 0; i <= n; i++) if(dp[i].fi == mx) ans += dp[i].se;cout << ans << '\\n';}return 0;
}

解法2：

定义$dp[i][j]$表示选了$i$个数，最后一个颜色为$j$的方案数。
转移的话需要注意的是如果$i\%k=1$，那么说明是新一段的第一个数，可以从之前的任意一种颜色转移，但是为了避免复杂度退化成 n 3 n^3 n3，加个小优化，维护一下和就行。

signed main() {
#ifdef JANGYIfreopen("input.in", "r", stdin);freopen("out.out", "w", stdout);
#endifios::sync_with_stdio(false);cin.tie(0); cout.tie(0);int T;cin >> T;while(T--) {int n, k; cin >> n >> k;vector<int> c(n + 1);for(int i = 1; i <= n; i++) cin >> c[i];vector<vector<mint>> dp(n + 1, vector<mint> (n + 1, 0));vector<vector<bool>> ok(n + 1, vector<bool> (n + 1));dp[0][0] = 1;ok[0][0] = true;vector<bool> can(n + 1);can[0] = true;vector<mint> sum(n + 1);sum[0] = 1;for(int i = 1; i <= n; i++) {for(int j = i; j >= 1; j--) {if(j % k == 1) {if(can[j / k]) {ok[j][c[i]] = true;dp[j][c[i]] += sum[j / k];}} else {if(ok[j - 1][c[i]]) {dp[j][c[i]] += dp[j - 1][c[i]];ok[j][c[i]] = true;}}if(j % k == 0 && ok[j][c[i]]) {can[j / k] = true;sum[j / k] += dp[j - 1][c[i]];}}}for(int i = n / k; i >= 0; i--) {if(can[i]) {cout << sum[i] << '\\n';break;}}}return 0;
}