2013
11-10

# 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: 82638882@163.com
import java.io.*;
public class Main
{
static int[] p,b,c,w;
static int a;
public static void main(String[] args) throws IOException
{
while(true)
{
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++)
{
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)

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));
}
}