POJ 3298 Antimonotonicity 差分约束

Antimonotonicity

Time Limit: 2000MS		Memory Limit: 65536K
Total Submissions: 2811		Accepted: 1202

Description

I have a sequence Fred of length n comprised of integers between 1 and n inclusive. The elements of Fred are pairwise distinct. I want to find a subsequence Mary of Fred that is as long as possible and has the property that:

Mary₀ > Mary₁ < Mary₂ > Mary₃ < ...

Input

The first line of input will contain a single integer T expressed in decimal with no leading zeroes. T will be at most 50. T test cases will follow.

Each test case is contained on a single line. A line describing a test case is formatted as follows:

n Fred₀ Fred₁ Fred₂ ... Fred_n-1.

where n and each element of Fred is an integer expressed in decimal with no leading zeroes. No line will have leading or trailing whitespace, and two adjacent integers on the same line will be separated by a single space. n will be at most 30000.

Output

For each test case, output a single integer followed by a newline --- the length of the longest subsequence Mary of Fred with the desired properties.

Sample Input

4
5 1 2 3 4 5
5 5 4 3 2 1
5 5 1 4 2 3
5 2 4 1 3 5

Sample Output

1
2
5
3
代码：

//转换=，A-B=x相当于A-B<=X和A-B>=X；
// 即  A - B <= x && B - A <= -x 
// 再加上 A - B >= 1 即 B - A <= -1 
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std ;
#define MAX 100010 
struct node
{
	int s ,e , w ;
}qe[MAX*2] ;
#define INF 25797524
int d[1010] ;
int main()
{
	int i , j , n ,m , flash;
	int u , v , w , len ;
	char a ;
	while( scanf( "%d%d" , &n , &m ) != EOF )
	{ 
		len = 0 ;
		for( i = 1 ; i <= m ;i++ )
		{  
			scanf( " %c" , &a ) ;// 加个空格就可以把回车吃掉
			if( a == 'P' )
			{
				scanf( "%d%d%d" , &u , &v , &w ) ;
			        len++ ;
					qe[len].s = v ;
					qe[len].e = u ;
					qe[len].w = w ;
					len++ ;
					qe[len].s = u ;
					qe[len].e = v ;
					qe[len].w = -w ;
			}
			else if( a == 'V' ){
				scanf( "%d%d" , &u , &v ) ;
				len++ ;
				qe[len].s = u ;
				qe[len].e = v ;
				qe[len].w = -1 ;
			}
		}
		for( i = 2 ; i <= n ;i++)
			d[i] = INF ;
		d[1] = 0 ;
		for( i = 1; i <= n ;i++)
		{  
			for( j = 1; j <= len ;j++)
			{    flash = 1 ;
				if( d[qe[j].e]  >  d[qe[j].s] + qe[j].w )
					d[qe[j].e] = d[qe[j].s] + qe[j].w ;
 			}
		}
		int ok = 0 ;
		for( i = 1;  i <= len ;i++)
			if( d[qe[i].e] > d[qe[i].s] + qe[i].w )
			{
				ok  = 1 ;// 存在负的 则是 错误的
				break ;
			}
			if(ok) printf( "Unreliable\n" ) ;
			else printf("Reliable\n" ) ;
	} 
}