CF1497E2题解

· · 题解

题解没有 O(nk) 的 dp 做法，于是写一下。尽管预处理是 O(n\sqrt V) 的。

首先注意到应该有一定的贪心性质，在分段数相同的时候，你希望最后一个分割点更靠后。
然后考虑完全平方数有什么性质，其因子的次数都是偶数。
两个数相乘为一个完全平方数，本质上和他们所含有的偶数次方因子没有关系。只需把这些除掉就转化成了两个数相等的问题。预处理一个小常数单根号是容易做的，可以进一步优化但没有必要。

再考虑你转化后怎么做，相等的情况可以记一个 to_i 表示和 i 相同的上一个，格式化想到一个 f_{i,j} 表示前 i 个分 j 段的最少段数，发现是没有办法转移的，因为你不知道上一个分段点。
不妨用 0/1 把答案和转移点都记下来，每次从前转移。

但是你其实并不需要决策转移点，因为考虑前 i 个和前 i-1 个的区别本质就是第 i 个位置造成的冲突。
记分段点为 x，即最后一段的开头。
如果 x>to_i，该冲突在这一段不存在，可以直接继承 f_{i,j}。
否则冲突存在，处理方法是改掉一个或者新开一段。
也就是从 f_{i-1,j} 或者 f_{i-1,j-1} 转移。

这个转移为什么是对的，考虑你在计算 f_{i,j} 的时候前面的东西应该被算完了，并且你已经记住了它的最优决策点。
所以每个位置的最优决策点应该是唯一的，所以就省去了枚举决策点的一个 k。

具体的方程可以看代码和注释，是简单的。主要想分享这种预先知道决策点复杂度省一个 k 的东西。

submission

#include<bits/stdc++.h>
using namespace std;
int a[200010],f[200010],dp[200010][21][2];
unordered_map<int,int> mp,to;
void solve(){
    int n,k;cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++){
        int now=a[i];
        for(int j=2;j*j<=now;j++){
            while(now%(j*j)==0) now/=(j*j);
        }
        a[i]=now;
    }
    mp.clear();
    for(int i=1;i<=n;i++){
        if(mp[a[i]]) to[i]=mp[a[i]];
        else to[i]=0;
        mp[a[i]]=i;
    }
    for(int i=0;i<=n;i++)
        for(int j=0;j<=k;j++) dp[i][j][1]=1e9,dp[i][j][0]=0;
    dp[1][0][0]=1,dp[1][0][1]=1;
    dp[1][1][0]=1,dp[1][1][1]=1;
    for(int i=2;i<=n;i++){
        for(int j=0;j<=min(i,k);j++){
            int x=to[i];
            if(dp[i-1][j][0]>x) dp[i][j][0]=dp[i-1][j][0],dp[i][j][1]=dp[i-1][j][1];
            else
            {
                if(dp[i-1][j][1]+1<=dp[i][j][1]){
                    dp[i][j][0]=i;
                    dp[i][j][1]=dp[i-1][j][1]+1;
                }
                if(j&&(dp[i-1][j-1][1]<dp[i][j][1]||(dp[i-1][j-1][1]==dp[i][j][1]&&dp[i-1][j-1][0]>dp[i][j][0]))){
                    dp[i][j][0]=dp[i-1][j-1][0];
                    dp[i][j][1]=dp[i-1][j-1][1];
                }
            }
        }
    } 
    int ans=1e9;
    for(int i=0;i<=k;i++){
        ans=min(ans,dp[n][i][1]);
    }
    cout<<ans<<'\n';
    return ;
}
signed main(){
    //freopen("seq.in","r",stdin);
    //freopen("seq.out","w",stdout);
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int T;cin>>T;while(T--) solve();
}
/*
尽量往后划 
f[i][j][0/1]=f[i-1][j][0/1]
to[i]
if(f[i-1][j][0]>to[i]) f[i][j][0/1]=f[i-1][j][0/1]
else 
f[i][j][0]=i,f[i][j][1]=f[i-1][j]+1
f[i][j][0]=f[i-1][j-1][0],f[i][j][1]=f[i-1][j-1][1]
*/