两个子序列dp问题

在一个序列上做一些修改，求一些最小操作数，最小划分数，最小长度之类的很多都可以用dp来解，也有一定套路，最近连碰两个。就放一起了。

CF1699D （dp，预处理）

Codeforces Round #804 (Div. 2) – Mxrurush – 博客园 (cnblogs.com)

这里D题的思路是做 /(dp/) 然后用一些预处理找到转移条件。

下面题也大同小异，是预处理用来优化枚举。只是预处理更加复杂，需要贪心+双指针。

CF1392 E1E2（dp，双指针，贪心）

题意

划分一个长度为 /(n/) 的序列，保证每个划分中不存在两个数字乘积是完全平方数。

另外在E2中可以有 /(k/le 20/) 次操作，每次可以把一个数字变成任意值。

求最小的划分数。

思路

先看E1。

把每个数字的质因子变成 /(p^{k/%2}/) 的形式，也就是把平方因子都干掉，之后就不用判断 /(a*b == 完全平方数 ？/) 只用判断划分中有没有 /(a == b ?/) 就行了。

能这样做的原因是完全平方数质因数都是偶数。

之后按上面结论做一个简单的序列划分贪心即可。

E2 可以对一些数字修改，这样的带修的子序列或者子段问题很多时候我们可以用dp解决。

（其实这里的修成任意数和上一个题里的删数在dp上是一样的，都是不再考虑的意思）

我们考虑 $dp[i][j] $ 表示用了 /(j/) 次的修改次数，/([1,i]/) 的最小划分数，显然 /(min(dp[n][])/) 就是答案。

考虑状态转移。先随便考虑一个前状态 /(dp[k][p]/) 如果它可以转移到现态，可以想到应该满足如下条件：

1. /(k < i,~p /le j/)
2. /(k/) 是划分的一个终点，/([k+1,i]/) 是一个划分段。

关键在如何找到 /(k/) ，数据规模不允许我们暴力枚举。此时发现 /(p/) 还未被讨论。考虑从 /(dp[k][p] => dp[i][j]/) 产生的新划分消耗了 /(j – p/) 次操作。我们对划分做一个贪心优化转移：我们尽可能的利用这些操作使得 /([k+1,i]/) 尽可以的长。

那么每次转移可以表示为 /(dp[i][j] = min/{dp[f(i,j-p)][p] + 1/}/) 。其中 /(f(k,j-p)/) 表示从以 /(i/) 为右端点，有 /(j-p/) 次操作的极长划分的左端点。

现在问题只剩下如何求 /(f/) 。

对于求极长子段的问题，我们很多时候可以用双指针求得。此处在E1的基础下，很容易写。因此只要对 /(k/) 的每个取值跑双指针即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
#include<queue>
#include<map>
#include<stack>
#include<string>
#include<random>
#include<iomanip>
#define yes puts("yes");
#define inf 0x3f3f3f3f
#define ll long long
#define linf 0x3f3f3f3f3f3f3f3f
#define ull unsigned long long
#define endl '/n'
#define int long long
#define rep(i,a,n) for(int i = a;i <= n;i++)
#define per(i,n,a) for(int i = n;i >= a;i--)
using namespace std;
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand() % x;}
typedef pair<int,int> PII;
const int MAXN =10 + 2e5 ,mod=1e9 + 7;
vector<int> to;
void init() {
    to.resize(1e7 + 1);
    rep(i,0,1e7) to[i] = i;
    rep(i,2,4e3) {
        for(int j = i * i;j <= 1e7;j += i * i)
            while(to[j] % (i * i) == 0) to[j] /= i * i;
    }
}
int s[10000010];
void solve()
{    
    int n,k; cin >> n >> k;
    vector<int> a(n + 1);
    rep(i,1,n) cin >> a[i], a[i] = to[a[i]];
    vector<vector<int>> f(n + 1,vector<int>(21));
    rep(ct,0,k) {
        for(int i = 1,j = 1,now = 0;i <= n;i ++) {
            // f[i][ct]   [j,i]
            s[a[i]] ++;
            if(s[a[i]] >= 2) {
                if(now < ct) now ++;
                else {
                    while(now >= ct) {
                        now -= s[a[j]] >= 2;
                        s[a[j]] --;
                        j ++;
                    }
                    now ++;
                }
            }
            f[i][ct] = j;
        }
        rep(i,1,n) s[a[i]] = 0;
    }
    vector<vector<int>> dp(n + 1,vector<int>(21,linf));
    rep(j,0,k) dp[0][j] = 0;
    rep(i,1,n) {
        rep(j,0,k) {
            rep(p,0,j) {
                dp[i][j] = min(dp[i][j], dp[f[i][p] - 1][j - p] + 1);
            }
        }
    }
    cout << *min_element(dp[n].begin(),dp[n].end()) << endl;
}
signed main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    init();
    int T;cin>>T;
    while(T--)
        solve();

    return 0;
}

最近在写写 python ，再给一版 python 代码

MAXN = 10**7 + 5
INF = 10**18

to = [i for i in range(MAXN)]
for i in range(2,10**4):
    for j in range(i * i,MAXN,i * i):
        while to[j] % (i * i) == 0:
            to[j] //= i * i

_t = int(input())

s = [0] * MAXN
for __ in range(_t):
    n,k = map(int,input().split())
    a = list(map(int,input().split()))
    a = [0] + a
    for i in range(1,n + 1):
        a[i] = to[a[i]]
    
    f = [[0] * (k + 1) for _ in range(n + 2)]
    for ct in range(k + 1):
        j,now = 1,0
        for i in range(1,n + 1):
            s[a[i]] += 1
            if s[a[i]] >= 2:
                now += 1
                if now > ct:
                    while now > ct:
                        now -= s[a[j]] >= 2
                        s[a[j]] -= 1
                        j += 1
            f[i][ct] = j
        for x in a: s[x] = 0
    
    dp = [[INF] * (k + 1) for _ in range(n + 2)]
    for j in range(0,k + 1): dp[0][j] = 0

    for i in range(1,n + 1): 
        for j in range(k + 1): 
            for p in range(j + 1):
                dp[i][j] = min(dp[i][j], dp[f[i][p] - 1][j - p] + 1)
                
    print(min(dp[n][0:]))