紫书例题 10-29 UVa 1642（最优连续子序列）

这类求最优连续子序列的题一般是枚举右端点，然后根据题目要求更新左端点，

一般是nlogn，右端点枚举是n，左端点是logn

难点在于如何更新左端点

用一些例子试一下可以发现

每次加进一个新元素的时候

前面的元素都要再取一遍gcd

然后gcd同的时候i尽量大

为了去重，我们需要排序，用相邻元素比较

保留下来最优的一些区间，然后更新答案

#include<cstdio>

#include<algorithm>

#include<vector>

#define REP(i, a, b) for(int i = (a); i < (b); i++)

using namespace std;

typedef long long ll;

const int MAXN = 112345;

ll a[MAXN];

struct node

{

	ll g;

	int p;

	bool operator < (const node& rhs) const

	{

		return (g < rhs.g) || (g == rhs.g && p < rhs.p);

	}

};

ll gcd(ll a, ll b) { return !b ? a : gcd(b, a % b); }

int main()

{

	int n, T;

	scanf("%d", &T);

	while(T--)

	{

		scanf("%d", &n);

		REP(i, 0, n) scanf("%lld", &a[i]);

		vector<node> g;

		ll ans = 0;

		REP(i, 0, n)

		{

			g.push_back(node{0, i});

			REP(j, 0, g.size())

				g[j].g = gcd(g[j].g, a[i]);

			sort(g.begin(), g.end());

			vector<node> newg;

			REP(j, 0, g.size())

				if(j == 0 || g[j].g != g[j-1].g)

				{

					newg.push_back(g[j]);

					ans = max(ans, g[j].g * (i - g[j].p + 1));

				}

			g = newg;

		}

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

	}

	return 0;

}

巴特西

紫书例题 10-29 UVa 1642（最优连续子序列）

最新文章

热门文章

巴特西

紫书 例题 10-29 UVa 1642（最优连续子序列）

最新文章

热门文章

紫书例题 10-29 UVa 1642（最优连续子序列）