取数游戏 game bzoj-1978 BeiJing-2010

题目大意：给定一个$n$个数的$a$序列，要求取出$k$个数。假设目前取出的数是$a_j$，那么下次取出的$a_k$必须保证：$j<k$且$gcd(a_j,a_k)/reL$。问最多能取出多少个数。

注释：$1\le n\le 5\cdot 10^4$，$2\le L \le a_i\le 10^6$。

想法：

显然可以用动态规划解决。

状态：$dp_i$表示强制选第$i$个数，前$i$个数中最多能取多少个数。

转移是$O(n^2)$的。

接下来，我们思考：如何才能优化这个过程。

有一个性质：

假设存在$i<j<k$，使得$m|a_i,m|a_j,m|a_k,m\ge L$，那么我们选择用$j$更新$k$而不是$i$，原因在于$f_j$完全可以在$i$构成的序列中，后面加上$j$因为$gcd(a_i,a_j)\ge m\ge L$。

所以我们只需要更新出$lst$数组：$lst_i$表示枚举到当前的$a$，可以被$i$整除的最大的下标（时间戳）最大是多少。

接下来，我们既可以通过$lst$数组来更新$dp$数组。

具体地：每次我们枚举当前元素的时候，将当前元素质因数分解，动态更新$lst$数组。

如何更新$f$数组呢？

我们只需要将$lst$数组的值直接加到$f$上可。

总时间复杂度$O(n\sqrt n)$。

Code：

#include <bits/stdc++.h>

#define N 50010

#define M 1000010

using namespace std;

int f[N],mx[M],a[N];

inline char nc() {static char *p1,*p2,buf[100000]; return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;}

int rd() {int x=0; char c=nc(); while(!isdigit(c)) c=nc(); while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=nc(); return x;}

int main()

{

	int n=rd(),L=rd(); for(int i=1;i<=n;i++) a[i]=rd();

	for(int i=1;i<=n;i++)

	{

		int now=0;

		for(int j=1;j*j<=a[i];j++)

		{

			if(a[i]%j==0)

			{

				if(j>=L) now=max(now,mx[j]);

				if(j*j!=a[i])

				{

					if(a[i]/j>=L) now=max(now,mx[a[i]/j]);

				}

			}

		}

		f[i]=now+1;

		for(int j=1;j*j<=a[i];j++)

		{

			if(a[i]%j==0)

			{

				if(j>=L) mx[j]=max(mx[j],f[i]);

				if(j*j!=a[i])

				{

					if(a[i]/j>=L) mx[a[i]/j]=max(mx[a[i]/j],f[i]);

				}

			}

		}

	}

	int ans=0; for(int i=1;i<=n;i++) ans=max(ans,f[i]);

	printf("%d\n",ans);

	return 0;

}

小结：优化$dp$的好题。

巴特西

[bzoj1978][BeiJing2010]取数游戏 game_动态规划_质因数分解

取数游戏 game bzoj-1978 BeiJing-2010

最新文章

热门文章