USACO2016OPEN PLATINUM 262144

wjh15101051's space

卧薪尝胆，厚积薄发。

Date: Wed Sep 19 17:15:34 CST 2018

In Category: NoCategory

Description：

给 $n$ 个数，每次可以把相邻两个相同的数合成比他们大一的数，问最后最终能得到的最大的数是多少。

$1\le n \le 270000,1\le a_i\le 40$

Solution1：DP

$f[i][j]$ 表示 $i$ 位置上的数合成数 $j$ 的区间右端点 $+1$ 最小是多少，转移为 $f[i][j]=f[f[i][j-1]][j-1]$ 。

Code1：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

#define MAXN 270010

int n;

int a[MAXN];

int f[MAXN][61];

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)scanf("%d",&a[i]);

	memset(f,0,sizeof(f));

	for(int i = 1;i <= n;++i)f[i][a[i]] = i + 1;

	int ans = 0;

	for(int i = 2;i <= 60;++i)

	{

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

		{

			if(!f[j][i])f[j][i] = f[f[j][i - 1]][i - 1];

			if(f[j][i])ans = i;

		}

	}

	cout << ans << endl;

	return 0;

}

Solution2：贪心

从小到大枚举每个数，如果连续的偶数项，那么显然两两合成，如果奇数项，那么最终一定会剩一个，也就是说两边必定分离，那就每边 $\frac{i+1}2$ 个，中间用 $-1$ 分隔开即可。

Code2：

没有代码。

In tag: DP-DP 算法-贪心

wjh15101051