首页 > 专题系列 > Java解POJ > POJ 2082 Terrible Sets [解题报告] Java
2013
11-10

POJ 2082 Terrible Sets [解题报告] Java

Terrible Sets

问题描述 :

Let N be the set of all natural numbers {0 , 1 , 2 , . . . }, and R be the set of all real numbers. wi, hi for i = 1 . . . n are some elements in N, and w0 = 0.

Define set B = {< x, y > | x, y ∈ R and there exists an index i > 0 such that 0 <= y <= hi ,∑0<=j<=i-1wj <= x <= ∑0<=j<=iwj}

Again, define set S = {A| A = WH for some W , H ∈ R+ and there exists x0, y0 in N such that the set T = { < x , y > | x, y ∈ R and x0 <= x <= x0 +W and y0 <= y <= y0 + H} is contained in set B}.

Your mission now. What is Max(S)?

Wow, it looks like a terrible problem. Problems that appear to be terrible are sometimes actually easy.

But for this one, believe me, it’s difficult.

输入:

The input consists of several test cases. For each case, n is given in a single line, and then followed by n lines, each containing wi and hi separated by a single space. The last line of the input is an single integer -1, indicating the end of input. You may assume that 1 <= n <= 50000 and w1h1+w2h2+…+wnhn < 109.

输出:

Simply output Max(S) in a single line for each case.

样例输入:

3
1 2
3 4
1 2
3
3 4
1 2
3 4
-1

样例输出:

12
14

解题代码:

//* @author: [email protected]
import java.io.*;
public class Main
{
 static int[] p,b,c,w;
 static int a;
 public static void main(String[] args) throws IOException
 {
  InputStreamReader is=new InputStreamReader(System.in);
  BufferedReader in=new BufferedReader(is);
  while(true)
  {
	String[] ss=in.readLine().split(" ");
	a=Integer.parseInt(ss[0]);
	if(a==-1)break;
	p=new int[a+2];
	b=new int[a+1];
	c=new int[a+1];
	w=new int[a+1];
	for(int i=1;i<=a;i++)
	{
		ss=in.readLine().split(" ");
		w[i]=Integer.parseInt(ss[0]);
		p[i]=Integer.parseInt(ss[1]);
	}
	p[0]=p[a+1]=-1;
	long max=0;
	for(int i=1;i<=a;i++)
	{
		b[i]=1;
		int j=i;
		while(p[j-b[j]]>=p[i])
		{
			j-=b[j];
			b[i]+=b[j];
		}
	}
	for(int i=a;i>0;i--)
	{
		c[i]=1;
		int j=i;
		while(p[j+c[j]]>=p[i])
		{
			j+=c[j];
			c[i]+=c[j];
		}
	}
	for(int i=1;i<=a;i++)
	{
		int total=w[i];
		for(int u=1;u< c[i];u++)
			total+=w[u+i];
		for(int u=1;u< b[i];u++)
			total+=w[i-u];
		long ans=total*p[i];
		max=Math.max(ans, max);
	}
	System.out.println(max);
   }
 }
}

  1. 这道题这里的解法最坏情况似乎应该是指数的。回溯的时候
    O(n) = O(n-1) + O(n-2) + ….
    O(n-1) = O(n-2) + O(n-3)+ …
    O(n) – O(n-1) = O(n-1)
    O(n) = 2O(n-1)

  2. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  3. 漂亮。佩服。
    P.S. unsigned 应该去掉。换行符是n 不是/n
    还可以稍微优化一下,
    int main() {
    int m,n,ai,aj,bi,bj,ak,bk;
    while (scanf("%d%d",&m,&n)!=EOF) {
    ai = sqrt(m-1);
    bi = sqrt(n-1);
    aj = (m-ai*ai-1)>>1;
    bj = (n-bi*bi-1)>>1;
    ak = ((ai+1)*(ai+1)-m)>>1;
    bk = ((bi+1)*(bi+1)-n)>>1;
    printf("%dn",abs(ai-bi)+abs(aj-bj)+abs(ak-bk));
    }
    }