学步园

晕死,,,反正是对不了..

都是自己写代码的风格不行呀,,

怎么也写不对了- -#

烦死了都,,,

不知道是怎么错了..好像和别人写的差不多呀

自己的:

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <string>

#define max(a, b) (a) > (b) ? (a) : (b)

using namespace std;

struct node{
	int a;
	int b;
}q[1111];

int n;

int map[1111][1111];

int d[1111];

bool Judge(int i, int j)
{
	if (q[i].a < q[j].a && q[i].b < q[j].b || q[i].a < q[j]. b && q[i].b < q[j].a)
	{
		return true;
	}
	return false;
}

int dp(int i)
{
	if (d[i] > 0)
	{
		return  d[i];
	}
	int ans = 1;
	for (int j = 0; j < n; j++)
	{
		if (map[j][i])
		{
			ans = max(ans, dp(j) + 1);
		}
	}
	return ans;
}

int main()
{
	int T;
	scanf("%d", &T);
	while (T--)
	{
		memset(map, 0, sizeof(map));
		scanf("%d", &n);
//		if (n == 0)
//		{
//			printf("-1\n");
//			continue;
//		}
		for (int i = 0; i < n; i++)
		{
			scanf("%d%d",&q[i].a, &q[i].b);
		}
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
			{
				if (Judge(i, j))
				{
//					cout << "i = " << i << " " << "j = " << j << endl; 
					map[i][j] = 1;
				}
			}
		}
		int t = 0;
		memset(d, 0, sizeof(d));
		for (int i = 0; i < n; i++)
		{
			d[i] = dp(i);
//			printf("dp[%ds] = %d", i + 1, d[i]);
//			cout << endl;
			t = max(t, d[i]);
		}
		printf("%d\n", t);
	}
//	system("pause");
	return 0;
}

别人的:

//在线提交地址：http://acm.nyist.net/JudgeOnline/problem.php?pid=16
//另附0ms	 236kb的DP思路：按边长降序排序，用类似LIS的方法求解，只是比较元素大小的方法变成了比较长和宽
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define maxn 1008

using namespace std;

int G[maxn][maxn], a[maxn], b[maxn], d[maxn], n;

int dp(int i){
  int& ans = d[i];
  if (ans > 0) return ans;
  ans = 1;
  for(int j = 1; j <= n; ++j) if(G[i][j]) ans = max(ans, dp(j)+1);
  return ans;
}
int main(){
  int t;
  scanf("%d", &t);
  while(t--){
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) scanf("%d%d", a+i, b+i);
    memset(G, 0, sizeof(G));
    for(int i = 1; i <= n; ++i)
      for(int j = 1; j <= n; ++j) if((a[i]>a[j]&&b[i]>b[j])||(a[i]>b[j]&&b[i]>a[j]))
        G[i][j] = 1;
    int ans = -1, t, s;
    memset(d, 0, sizeof(d));
    for (int i = 1; i <= n; ++i) {
      t = dp(i);
      if(ans < t) {ans = t; s = i;}
    }
    printf("%d\n", ans);
  }
//  system("pause");
  return 0;
}