POJ-1065 Wooden Sticks，排序+最长单减子序列！

题意：有一台机器处理木材，最开始需要一分钟准备，如果后面处理的木材比前面处理的木材更长更重，则不需要准备时间，否则需要分钟准备时间。

思路：按长度排序然后求重量的一个最长单减子序列就好了。

struct node

{

    int x,y;

}a[N];

int b[N];

int cmp(node a,node b)

{

    if(a.x!=b.x) return a.x<b.x;

    return a.y<b.y;

}

int main()

{

    int t ,n;

    scanf("%d",&t);

    while(t--)

    {

        scanf("%d",&n);

        for(int i=0;i<n;i++) scanf("%d%d",&a[i].x,&a[i].y);

            sort(a,a+n,cmp);

        memset(b,0,sizeof(b));

        int ans=0;

        for(int i=0;i<n;i++)

        {

            b[i]=1;

            for(int j=0;j<i;j++)

                if(a[i].y<a[j].y&&b[j]+1>b[i])

                b[i]=b[j]+1;

            ans=max(ans,b[i]);

        }

        printf("%d\n",ans);

    }

    return 0;

}

巴特西

POJ-1065 Wooden Sticks，排序+最长单减子序列！

最新文章

热门文章