The Fourth Dimension Space

枯叶北风寒，忽然年以残，念往昔，语默心酸。二十光阴无一物，韶光贱，寐难安； 不畏形影单，道途阻且慢，哪曲折，如渡飞湍。斩浪劈波酬壮志，同把酒，共言欢！ -如梦令

POJ 1065 Woon sticks

贪心和最长不上升子序列都过了 只是第二种方法的正确性不知道该怎么证明？？？
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

struct point
{

    int x,y;
    bool operator <(point other)
    {
        if(x==other.x)
            return y<other.y;
        else
            return x<other.x;
    }
}a[5001];
int dp[5001];


int main()
{
    int t;
    scanf("%d",&t);
    int i,j,k;
    int n;
    for(k=1;k<=t;k++)
    {
        int res=1;
        scanf("%d",&n);
        for(i=1;i<=n;i++)
            scanf("%d%d",&a[i].x,&a[i].y);
        sort(a+1,a+n+1);
        dp[1]=1;
        for(i=2;i<=n;i++)
        {

            int mm=0;
            for(j=1;j<i;j++)
            {
                if((a[i].x<a[j].x||a[i].y<a[j].y)&&dp[j]>mm)
                    mm=dp[j];
            }
            dp[i]=mm+1;
        }
        for(i=2;i<=n;i++)
        {
            if(dp[i]>res)
                res=dp[i];
        }
        printf("%d\n",res);
    }
    return 0;


}

posted on 2010-03-20 15:25 abilitytao 阅读(281) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理