11
3
2015
0

【usaco 2014open】【前缀和优化dp】Fair Photography

FJ的N(1 <= N <= 100,000)头牛站在一个数轴的不同点上。第I头牛站在xi位置(0...1,000,000,000),并有一个品种标志BI(G或H)。没有两头牛站在同一位置。

FJ想给他的牛们拍照。他希望照片中牛的品种数量是均衡的。例如,一个照片中全是H牛是可以的,一个照片中有27个G牛和27H牛也是可以的,但一个照片10个G牛和9个H牛不可以)。帮助FJ计算出让他满意的照片中最远位置的两头牛的距离。有可能在FJ的照片中只有一头牛,这时计算的距离为0.

 

PROBLEM NAME: fairphoto

INPUT FORMAT:

* Line 1: The integer N.

* Lines 2..1+N: Line i+1 contains x_i and b_i.

SAMPLE INPUT (file fairphoto.in):

6

4 G

10 H

7 G

16 G

1 G

3 H

INPUT DETAILS: There are six cows with breeds (from left to right) G, H, G, G, H, G.

OUTPUT FORMAT:

Line 1: A single integer indicating the maximum size of a fair photo.

SAMPLE OUTPUT (file fairphoto.out):

7

OUTPUT DETAILS: The largest fair photo Farmer John can take is of the middle 4 cows, containing 2 Holsteins and 2 Guernseys.


我第一次做的代码:

前缀和简单记录区间两种奶牛个数

数组不够大且超时,只得了30分

前缀和记录:

 for(int i=1;i<=n;i++)
{
f[i][i]=0;
if(a[i].ch=='H') sumh[i]++;
if(a[i].ch=='G') sumg[i]++;
}
for(int i=1;i<=n;i++)
{
sumh[i]+=sumh[i-1];
sumg[i]+=sumg[i-1];
}

#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<string>
#define inf 1000000000
#define maxn 300000
#define maxm 500+100
#define eps 1e-10
#define ll long long
#define pa pair<int,int>
#define for0(i,n) for(int i=0;i<=(n);i++)
#define for1(i,n) for(int i=1;i<=(n);i++)
#define for2(i,x,y) for(int i=(x);i<=(y);i++)
#define for3(i,x,y) for(int i=(x);i>=(y);i--)
#define mod 1000000007
using namespace std;
/***************
date:10-30
time:5:00-5:34 baoli
note:
***************/
inline ll int read()
{
	ll int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=10*x+ch-'0';ch=getchar();}
	return x*f;
}
//const int M=1e5+10;
const int M=7000;
struct moo{int pos;char ch;}a[M];
int n,f[M][M],sumh[M],sumg[M],pos[M],ans=0;//too large?
bool cmp(moo x,moo y)
{
	return x.pos<y.pos;
}
int main()
{
//	freopen("fairphoto.in","r",stdin);
//	freopen("fairphoto.out","w",stdout);
		n=read();
		memset(f,255,sizeof(f));
		memset(sumh,0,sizeof(sumh)),memset(sumg,0,sizeof(sumg));
		for(int i=1;i<=n;i++)
		{a[i].pos=read();a[i].ch=getchar();}
		sort(a+1,a+n+1,cmp);
		for(int i=1;i<=n;i++)
		{
			f[i][i]=0;
			if(a[i].ch=='H') sumh[i]++;
			if(a[i].ch=='G') sumg[i]++;
		}
		for(int i=1;i<=n;i++)
		{
			sumh[i]+=sumh[i-1];
			sumg[i]+=sumg[i-1];
		}
		for(int i=1;i<=n;i++)
			for(int j=i+1;j<=n;j++)
			{
				int tmp1=sumh[j]-sumh[i-1],
				tmp2=sumg[j]-sumg[i-1];
				if(tmp1==0||tmp2==0||tmp1==tmp2)
				{
					f[i][j]=max(f[i][j],a[j].pos-a[i].pos);
				}
				ans=max(ans,f[i][j]);
			}
			printf("%d\n",ans);
			return 0;
}

正解:

1、将两种奶牛分别看做-1和1。

原问题转化为:已知一个类似0/1(-1与1)串,求满足下列任一条件的最大区间:该区间内全部为-1,全部为1或者1与-1数量相等。

前缀和为0则表明该区间两种牛数量相同。常见处理角度,使问题简化许多。

2、O(n)算法:

定义数组last[x]记录满足sum[pos]==x的最小pos

注意:数组下标不为负。将所有x统一加上n

遍历所有前缀和,找到与当前奶牛i前缀和相等且距离最远的奶牛位置j

则[j+1,i]区间为满足第三种情况的区间。

对于前两种情况,一同用num[]记录判断即可

 

Category: 前缀和 | Tags: | Read Count: 905

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com