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 阅读(236) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理