首页 > ACM题库 > HDU-杭电 > HDU 3674-Evaluating Functions[解题报告]HOJ
2014
11-30

HDU 3674-Evaluating Functions[解题报告]HOJ

Evaluating Functions

问题描述 :

A teleport machine – a special kind of machine capable of moving objects from one place to another instantaneously, without passing through the intervening space – has just been invented. Out of curiosity, you went to the laboratory and asked if you could have a try. Although even the engineers who have designed this machine can’t control where the object entering the machine will end up, they have told you the way the teleport machine operates:

David Shopping

In the interior of the teleport machine you may find a special structure (as illustrated above). There are N cylinders of possibly different integer heights, and a special (yet unknown to you) value had been assigned to each of them in the following way:

Suppose the heights of the cylinders are recorded in the array H[] , the values assigned to them are recorded in the array value[] , and we are currently calculating the value for cylinder X (i.e., valuex . Before this process is executed, valuex will be set to zero, and we initialized a pointer, P , which should be pointing to X at the beginning)

0.
Let P = P – 1 . (i.e., modifies the pointer P so that it now points to the cylinder on the left side of the current cylinder P ). If there’s none (P = = NULL) , or Hp > Hx , then let P = X , and go to step 2; otherwise, proceed to the next step.
1.
Find the highest cylinder on the left side of the cylinder P , and let its height be H’ . If such cylinder exists, increase valuex by max{min{H’, Hx} – Hp, 0} , and go to step 0.
2.
Let P = P + 1 . (i.e., modifies the pointer P so that it now points to the cylinder on the right side of the current cylinder P ). If there’s none (P = = NULL) , or Hp > Hx , then terminate the process; otherwise, proceed to the next step.
3.
Find the highest cylinder on the right side of the current cylinder P , and let its height be H’ . If such cylinder exists, increase valuex by max{min{H’, Hx} – Hp, 0} , and go to step 2.

You have to enter two integers, the distance which you want to move the object, K , and the K -th largest value T among all N cylinders’ values. A serious malfunction will occur unless the numbers K and T are entered correctly. (It is easy to see that if we follow the process described above strictly, it takes O(N3) time to calculate all values; that is why the engineers can only use short-distance teleportation so far; however you wonder whether there exists a way to evaluate the function effectively so as to use the long-range transfer ability of this machine.)

Now you have to figure out what the value of T is, given the heights of all cylinders of the teleport machine and the distance you need to move the object. For example you find the machine has 5 cylinders, and the distance you want to move the object is 2. Their heights are 2 1 2 1 3 so your calculations (value ) are 2 0 2 0 2. After that the T which you should enter the second largest value is 2.

输入:

There are multiple test cases in the input file. Each test case starts with two integers N and K (1<=N<=2×105, 1<=K<=N) , the number of cylinders on the teleport machine, and the distance you want to move the object, respectively. Each of the following N lines contains one integer P (1<=P<=10^6) , the integer on the i -th line representing the height of the i -th cylinder. There is a blank line after each test case. A single line with N = 0 , K = 0 indicates the end of input file.

输出:

There are multiple test cases in the input file. Each test case starts with two integers N and K (1<=N<=2×105, 1<=K<=N) , the number of cylinders on the teleport machine, and the distance you want to move the object, respectively. Each of the following N lines contains one integer P (1<=P<=10^6) , the integer on the i -th line representing the height of the i -th cylinder. There is a blank line after each test case. A single line with N = 0 , K = 0 indicates the end of input file.

样例输入:

5 2 
2 
1 
2 
1 
3 

5 1 
4
5 
1 
1 
7 

0 0

样例输出:

Case 1: 2 
Case 2: 8

#include<stdio.h>
#include<algorithm>

#define N 200009
typedef long long LL;

using namespace std;

int n,m,a[N],b[N],c[N],L[N],R[N];
LL d[N],s1[N],s2[N],sum[N];

LL max(LL aa, LL bb)
{
	if(aa > bb)return aa;
	return bb;
}

void make()
{
	int i,j,k,l;
	for(i=1;i<=n;i++)
	{
		k = i-1;
		while(k > 0 && a[k] <= a[i])k = b[k];
		b[i] = k;
	}
	
	for(i=n;i>0;i--)
	{
		k = i+1;
		while(k <= n && a[k] <= a[i])k = c[k];
		c[i] = k;
	}
}

int main()
{
	int i,j,k,l,cas=0;
	while(scanf("%d %d",&n,&m) != EOF)
	{
		if(n == 0 && m == 0)break;
		sum[0] = 0;
		for(i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
			sum[i] = sum[i-1] + a[i];
		}
		make();
		
		L[1] = a[1]; for(i=2;i<=n;i++) { L[i] = a[i]; if(L[i] < L[i-1])L[i] = L[i-1]; }
		R[n] = a[n]; for(i=n-1;i>0;i--) { R[i] = a[i]; if(R[i] < R[i+1])R[i] = R[i+1]; }
		
		
		s1[1] = 0;
		for(i=2;i<=n;i++)
		{
			s1[i] = s1[i-1] + max(L[i-1] - a[i], 0);
		}
		s2[n] = 0;
		for(i=n-1;i>0;i--)
		{
			s2[i] = s2[i+1] + max(R[i+1] - a[i], 0);
		}
		
		for(i=1;i<=n;i++)
		{
			d[i] = 0;
			k = b[i];
			if(k < 1)d[i] += s1[i];
			else
			{
				l = i-k-1; d[i] += (LL)l*a[i] - (sum[i-1]-sum[k]); 
			}
		//	printf("%d ",d[i]);
			k = c[i];
			if(k > n)d[i] += s2[i];
			else
			{//printf("%d %d %d\n",k,l*a[i], (sum[k-1]-sum[i]));
				l = k-i-1; d[i] += (LL)l*a[i] - (sum[k-1]-sum[i]);
			}
		//	printf("%d\n",d[i]);
		}
		sort(d+1, d+1+n);
		printf("Case %d: %I64d\n",++cas,d[n-m+1]);
	}
	return 0;
}

  1. 如果两个序列的最后字符不匹配(即X [M-1]!= Y [N-1])
    L(X [0 .. M-1],Y [0 .. N-1])= MAX(L(X [0 .. M-2],Y [0 .. N-1]),L(X [0 .. M-1],Y [0 .. N-1])
    这里写错了吧。