JDOJ3065 USACO-Open2016-Pt:262144


这道题名字非常奇怪……题目整的像WordPress默认随机生成似的QwQ

这是一道USACO铂金组的题,难度自然不小,不过是xqz题目拓展计划的题也很正常QwQ


题目大意:给你一个序列,你可以将其中的两个相邻且相同的元素合并并生成一个权值为这两个元素的值+1的新元素(即删掉其中一个,将剩余的那个元素+1放回去),问合并到最后所能达到的最大的那个数的权值。

这道题和另外一道困扰了我很久的题——“矩阵”十分的相似,一看就知道是区间DP。但是这道题并不能完全的用区间DP的方法写,因为“矩阵”保证所有矩阵之间可以随意相加,但是这道题并不能,因为它对合并操作有特殊要求。

这道题我们可以使用f[i][j]表示以i号元素作为左节点进行合并之后的唯一的元素权值=j的右节点。这道题我们将其设定为区间[x,y),表示第x号元素到第y-1号元素的这一区间。

那么,我们可以规定一个东西f[i][j],含义如上,那么这个东西的值是什么呢?

我们想,这个状态是由两个权值为j-1的点合成得到的。那么这道题的思路也就出来了QwQ

f[i][j]=f[ f[i][j-1] ][j-1]

虽然这是一个很奇怪的方程我并没有找到科学的证明方法,但是它就是对的啊有木有QwQ

最后一个问题:边界?

i的边界很简单,就是最多的元素个数嘛QwQ

那么j,也就是目标权值呢?

因为我不会手算那么我们就模拟跑一遍极端情况嘛QwQ

#include <cstdio>
#include <queue>

using namespace std;

queue<int>q;

int main()
{
	for(int i=1;i<=262144;++i) q.push(40);
	while(!q.empty())
	{
		int tmpa=q.front();
		q.pop();
		if(q.empty())
		{
			printf("%d",tmpa);
			return 0;
		}
		int tmpb=q.front();
		q.pop();
		if(tmpa!=tmpb)
		{
			q.push(tmpb);
			continue;
		}
		q.push(tmpa+1);
	}
	return 0;
}

输出了58。

于是我们j的最大值也知道了。由于有j-1所以j要从2开始循环。

最终就得到了答案。

附代码。

#include <cstdio>

int n,ans,intmp,f[270000][60];

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
	{
		scanf("%d",&intmp);
		f[i][intmp]=i+1;
	}
	for(int j=2;j<=58;++j)
		for(int i=1;i<=n;++i)
		{
			if(!f[i][j]) f[i][j]=f[f[i][j-1]][j-1];
			if(f[i][j]) ans=j;
		}
	printf("%d",ans);
}

 

声明:TonyZhao's Home|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - JDOJ3065 USACO-Open2016-Pt:262144


不骗了,不骗了。
A Simple OIer fighting tooth and nail.