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

CPP

#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]
*/

文章操作

相关推荐

评论

CF1497E2题解