脚本宝典收集整理的这篇文章主要介绍了CF1603C-Extreme Extension【整除分块,dp】，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

正题

题目链接:http://codeforces.com/contest/1603/problem/C

题目大意

定义一个序列(a)的(f(a))为你每次可以将序列中的一个数(z)分裂成(x+y=z)，然后再把(x,y)放回原来的位置，然后(f(a))表示把(a)变成不降序列的最少操作次数 给出一个长度为(n)的序列(a)，求它所有子区间的(f)值的和。

(1leq n,a_ileq 10^5)

解题思路

显然的每个数字(a_i)最终肯定是分解为(k-1)个(lfloorfrac{a_i}{k}rfloor)和一个(lceilfrac{a_i}{k}rceil)。 然后我们对于一个序列可以从右往左每个选择能分解的最小的次数来分肯定是最优的。 那么考虑暴力的(dp)，设(f_{i,j})表示现在第(i)个，所有左端点为(i)的区间中(a_i)分解的最前面那个为(k)的方案，然后倒着转移就好了。 考虑到(j)肯定是某个(lfloorfrac{a_i}{k}rfloor)，而(lfloorfrac{a_i}{k}rfloor)最多只有(2sqrt a_i)种取值，所以我们可以只枚举这些取值就好了。

时间复杂度：(O(nsqrt a_i))，略微卡常

code

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const ll N=1e5+10,P=998244353;
ll T,n,ans,a[N],f[2][N],g[2][N];
signed main()
{
	scanf("%lld",&T);
	while(T--){
		scanf("%lld",&n);
		for(ll i=1;i<=n;i++)
			scanf("%lld",&a[i]);
		ll o=0;
		g[o][a[n]]=1;ans=0;
		for(ll i=n-1;i>=1;i--){
			o^=1;ll m=a[i+1];
			for(ll l=1,r;l<=m;l=r+1){
				r=m/(m/l);
				ll x=m/l,w=(a[i]+x-1)/x,k=a[i]/w;
				f[o][k]+=f[!o][x]+(w-1)*g[!o][x];
				g[o][k]+=g[!o][x];
				ans+=f[!o][x];ans%=P;
				f[!o][x]=g[!o][x]=0;
			}
			g[o][a[i]]++;
		}
		for(ll l=1,r;l<=a[1];l=r+1)
			r=a[1]/(a[1]/l),(ans+=f[o][a[1]/l])%=P,f[o][a[1]/l]=g[o][a[1]/l]=0;
		printf("%lldn",ans);
	}
	return 0;
}

脚本宝典总结

以上是脚本宝典为你收集整理的CF1603C-Extreme Extension【整除分块,dp】全部内容，希望文章能够帮你解决CF1603C-Extreme Extension【整除分块,dp】所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。