首页 > ACM题库 > HDU-杭电 > HDU 2836-Traversal-动态规划-[解题报告]HOJ
2014
02-17

HDU 2836-Traversal-动态规划-[解题报告]HOJ

Traversal

问题描述 :

I arrive at a big lake and I have to cross it. Luckily, I’m a very good jumper, but the lake is too big to be crossed in one jump. On the shore, I find N boxes of different heights, set in a certain order. If I throw a box into the lake, it will float and it will have the same height as on the shore. This is good, because I intend to throw some boxes into the lake and get from one shore to the other by jumping from box to box. The only things to consider are:
The lake is big, so I must throw at least 2 boxes, which means that in order to cross the lake I have to make at least 3 jumps.
Not all the boxes have to be thrown; some of them may be ignored.
The boxes can be thrown into the lake only in the order they are found on the shore and I have to jump on them in this order.
The height difference between two consecutive boxes I use must be at most H meters, because I can jump a lot in length, but I have some problems with jumping in height.The height of a box doesn’t change when I jump on it.
I’m always able to jump from the shore to a box and from a box to the shore, no matter what the height of the box is.

Facing so many possibilities that respect the above conditions, I begin counting the number of possibilities that I have, instead of actually crossing the lake. I quickly find the answer and I wonder whether you can also find it as fast as I did.

Task

Write a program that determines the number of possibilities to cross the lake in the above conditions. Since the number can be quite big, you only have to output the remainder of this number, when divided by 9901.

输入:

There are multiple test cases. Each test case contains two integers N and H, separated by a space, representing the number of boxes and the maximum height difference between two consecutive boxes thrown into the lake. The following N lines contain the heights of the boxes, in the order the boxes are set on the shore. The (i+1)th line contains the height of the ith box.

输出:

There are multiple test cases. Each test case contains two integers N and H, separated by a space, representing the number of boxes and the maximum height difference between two consecutive boxes thrown into the lake. The following N lines contain the heights of the boxes, in the order the boxes are set on the shore. The (i+1)th line contains the height of the ith box.

样例输入:

4 2
1 
3 
7 
5

样例输出:

4

Hint
Explanation There are 4 possibilities: 1 3 1 3 5 3 5 7 5

/*
分析:
    (树状数组(或线段树)&&二分)&&DP。
    还是太水了,犯了一个很2的错误,想了一天。。。
    将high从小到大排序,然后,按照《输入顺序》对n个数
据进行循环求解,用二分找到在排过序的序列中的状态可以
推过来的数据的左右临界,则DP[i]=SUM(DP[j])+1(a<=j&&j<=b)
a、b为左右临界。遍历后,求SUM(DP[i])-n(去掉只有一个节点
的路径。)
    上面用DP[i]=SUM(DP[j])“+1”,这样在推的时候,根据是否
DP[前面的状态]>=1而判断出这个“前面的状态”有么有被求解过(
如果被求解过,那么这个前面的状态的节点,自然在当前的节点
的前面,这样递推才可以进行)。

                                              2013-03-13
*/

#include"stdio.h"
#include"string.h"
#include"stdlib.h"
const int N=100111;
const int Limit=9901;

int n,h;
int high[N],index[N],lowbit[N];
int C[N];
struct node{
	int index,high;
}E[N];

int cmp(const void *a,const void *b)
{
	node *c,*d;
	c=(node *)a;
	d=(node *)b;
	return c->high-d->high;
}
void update(int k,int dir)
{
	while(0<k && k<=n)
	{
		C[k]+=dir;
		C[k]%=Limit;
		k+=lowbit[k];
	}
}
int sum(int k)
{
	int p=0;
	while(0<k && k<=n)
	{
		p+=C[k];
		p%=Limit;
		k-=lowbit[k];
	}
	return p;
}
int solve()
{
	int i;
	int low,mid,up;
	int a,b,c,temp,x,z;
	int ans;

	memset(C,0,sizeof(C));
	E[0].high=-1111;
	qsort(E,n+1,sizeof(node),cmp);
	for(i=1;i<=n;i++)	index[E[i].index]=i;

	for(i=1;i<=n;i++)
	{
		temp=high[i]-h;
		low=1;up=n;
		while(low<=up)
		{
			mid=(low+up)>>1;
			if(E[mid].high<temp)    low=mid+1;
			else                    up=mid-1;
		}
		a=low;

		b=index[i];

		temp=high[i]+h;
		low=1;up=n;
		while(low<=up)
		{
			mid=(low+up)>>1;
			if(E[mid].high<=temp)	low=mid+1;
			else					up=mid-1;
		}
		c=low-1;

		if(a-1<=0)	x=0;
		else		x=sum(a-1);
		z=sum(c);
		update(b,z-x+1);
	}

	ans=sum(n)-n;
	while(ans<0)	ans+=9901;
	return ans;
}
int main()
{ 
	int i;
	for(i=1;i<=100000;i++)	lowbit[i]=i&(-i);
	while(scanf("%d%d",&n,&h)!=-1)
	{
		for(i=1;i<=n;i++)
		{
			scanf("%d",&high[i]);
			E[i].index=i;
			E[i].high=high[i];
		}
		printf("%d\n",solve());
	}
	return 0;
}

解题参考:http://blog.csdn.net/ice_crazy/article/details/8665067