hdu4293Groups

http://acm.hdu.edu.cn/showproblem.php?pid=4293

这题单拉出来写篇吧 确实不错的一题

将每个人说的话 转化一下 可以算出它处在哪个段中 题目就转换成了求不相交的最大段数 注意区间相同的情况

 #include <iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<stdlib.h>

 using namespace std;

 struct node

 {

     int l,r;

 }p[];

 int dp[],w[][];

 bool cmp(node a,node b)

 {

     if(a.l==b.l)

     return a.r<b.r;

     return a.l<b.l;

 }

 int main()

 {

     int i,j,k,n,a,b;

     while(cin>>n)

     {

         int g=;

         memset(w,,sizeof(w));

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

         {

             scanf("%d%d",&a,&b);

             if(a+b<n)

             {

                 g++;

                 p[g].l = a+;

                 p[g].r = n-b;

             }

         }

         sort(p+,p+g+,cmp);

         for(i = ; i <= g ; i++)

         {

             w[p[i].l][p[i].r]++;

             if(w[p[i].l][p[i].r]>(p[i].r-p[i].l+))

             w[p[i].l][p[i].r] = p[i].r-p[i].l+;

         }

         for(i =  ;i <= g ; i++)

         dp[i] = w[p[i].l][p[i].r];

         for(i = ; i <= g ; i++)

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

             if(p[i].l>p[j].r)

             dp[i] = max(dp[i],dp[j]+w[p[i].l][p[i].r]);

         int maxz = ;

         for(i = ; i <= g ; i++)

         maxz = max(dp[i],maxz);

         cout<<maxz<<endl;

     }

     return ;

 }