CF771E Bear and Rectangle Strips

摘要:
(i=j),同时展开两行,并从(i+1)开始选择一个矩阵。优化的关键在于,只有当(i=j)时,两条线的传递才能相交,否则两条线传递相对独立。最重要的一点是,当时我们只扩大了较小的生产线。

一、题目

点此看题

二、解法

首先设计出暴力 (dp),设 (dp[i][j]) 表示第一行考虑到 (i),第二行考虑到 (j) 的最大得分,先写转移:

  • 扩展第一行,可以无得分让 (i+1);可以选从 (i+1) 开始的和为 (0) 的段(选右端点最小的)
  • 扩展第二行,可以无得分让 (j+1),可以选从 (j+1) 开始的和为 (0) 的段。
  • (i=j) 时,同时扩展两行,选一个 (i+1) 开始的何为 (0) 的矩阵。

优化的关键是只有 (i=j) 时两行的转移才有交叉,否则两行的转移是相对独立的。一个至关重要的 ( t observation) 是当 (i ot=j) 时,我们只用扩展较小的那一行(指 (i,j) 比较出来较小)。因为如果不考虑第三种转移那么先扩展哪一行都是没关系的,否则扩展较小的一行就更有利于考虑第三种转移。

那么我们以 (dp[i][i]) 为转移主体,也就是考虑两行前 (i) 列的最大得分,对于 (i ot=j) 的扩展,我们只需要找到最小的 (j) 使得 (dp[i][j]=dp[i][i]+1)(或者 (dp[j][i]=dp[i][i]+1)),因为如果 (dp[i][j]>dp[i][i]+1) 那么说明某一行扩展多了,不符合上述结论所以自然不用考虑。

转移的时候维护那个 (j) 即可,时间复杂度 (O(n))

三、总结

考虑有效转移是优化的重要方法,也就是如果某一种转移的作用会在以后被解决那么我们就不用考虑它。

#include <cstdio>
#include <vector>
#include <iostream>
#include <map>
using namespace std;
const int M = 300005;
#define int long long
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int n,a[2][M],nx[3][M],s[3],dp[M];map<int,int> mp[3];
struct node
{
	int x,y,c;
};vector<node> vc[M];
void add(int x,int y,int c)
{
	dp[max(x,y)]=max(dp[max(x,y)],c);
	vc[min(x,y)].push_back(node{x,y,c});
}
void extend(int x,int y,int c)
{
	if(x<n)
	{
		add(x+1,y,c);
		int i=nx[0][x+1];
		if(i) add(i,y,c+1);
	}
	if(y<n)
	{
		add(x,y+1,c);
		int i=nx[1][y+1];
		if(i) add(x,i,c+1);
	}
	if(x<n && x==y)
	{
		int i=nx[2][x+1];
		if(i) add(i,i,c+1);
	}
}
signed main()
{
	n=read();
	for(int i=0;i<2;i++)
		for(int j=1;j<=n;j++)
			a[i][j]=read();
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<3;j++)
			mp[j][s[j]]=i;
		s[0]+=a[0][i];
		s[1]+=a[1][i];
		s[2]+=a[0][i]+a[1][i];
		for(int j=0;j<3;j++)
			if(mp[j][s[j]]) nx[j][mp[j][s[j]]]=i;
	}
	for(int i=0;i<n;i++)
	{
		extend(i,i,dp[i]);
		int l=n+1,r=n+1;
		for(node a:vc[i])
		{
			if(a.y==i && a.c==dp[i]+1)
				l=min(l,a.x);
			if(a.x==i && a.c==dp[i]+1)
				r=min(r,a.y);
		}
		if(l<=n) extend(l,i,dp[i]+1);
		if(r<=n) extend(i,r,dp[i]+1);
	}
	printf("%lld
",dp[n]);
}

免责声明:文章转载自《CF771E Bear and Rectangle Strips》仅用于学习参考。如对内容有疑问,请及时联系本站处理。

上篇[ABC209E] ShiritoriCF1392H ZS Shuffles Cards下篇

宿迁高防,2C2G15M,22元/月;香港BGP,2C5G5M,25元/月 雨云优惠码:MjYwNzM=

随便看看

simhash与Google的网页去重

Leoncom » simhash simhash与Google的网页去重 leoncom搜索技术4 comments 前几天去吃葫芦头的路上,大飞哥给详细的讲解了他在比较文本相似度实验时对Google的simhash方法高效的惊叹,回来特意去找了原文去拜读。 Simhash 传统IR领域内文本相似度比较所采用的经典方法是文本相似度的向量夹角...

进程间通信(四)

父子进程 我们的pipe调用探索的下一步就是使得子进程是与父进程不同的一个程序,而不是运行相同程序的另一个进程。我们可以使用exec调用来完成这个任务。这样做的一个困难就是通过exec执行的新进程需要知道访问哪一个文件描述符。在exec调用之后,就不再是这样的情况了,因为老进程已经被新的子进程所替代。我们可以通过向exec所执行的新进程传递文件描述符作为参数...

JS对img进行操作

<script type="text/javascript">var i = 1; var n;function showImg() { if (document.getElementById('img').getAttribute("src") == "images/1.jpg") {document.getElementById('img')...

VS 2005中毒后编译出现的错误及其解决过程

<!-- /* Font Definitions */ @font-face {font-family:宋体; panose-1:2 1 6 0 3 1 1 1 1 1; mso-font-alt:SimSun; mso-font-charset:134; mso-generic-font-family:auto; mso-font-p...

Examples Boost 1.41.0

Examples - Boost 1.41.0 Examples Allocation This example shows how to customise the allocation of memory associated withasynchronous operations. boost_asio/example/allocation...

git提交时如何忽略一些文件

起因 在使用git对软件进行版本管理的时候我们总有一些不需要提交到版本库里的文件和文件夹,或者在管理一个实际应用的开源项目的时候,不可以把带有数据库信息的文件上传到开源平台当中,这个时候我们就需要让git自动忽略掉一下文件。 关于.gitignore 为了让git忽略指定的文件和文件夹,我们需要在项目的根目录当中创建...