|code--------------------------------------------------------------------------------------------------+|001| /***************************************************************\                              |002|  *Author: 小呼                                                                               |003|  *Created Time: Sat 10 Jul 2010 09:56:40 AM CST                                                |004|  *File Name: b.cpp                                                                             |005|  *Description:贪心思想,将木棍按l，w排序，先处理第一个木棍，因为         |006|  *它前面放不下任何其他的木棍了,再依次往后检索是不是有木棍能在它的|007|  *后面处理而不用花时间setup，这时只需满足w大于它前面的木棍即可，   |008|  *因为经排序l一定大于前面的木棍，处理过的木棍都作上标记（mark[j]=1) |009| \***************************************************************/                              |010| //*========================*Head File*========================*\\                              |011|                                                                                                |012| #include
     
                                                                                   |013| #include
      
                                                                                    |014| #include
       
                                                                                     |015| /*----------------------*Global Variable*----------------------*/                              |016| int T,n;                                                                                       |017| bool mark[5001];                                                                               |018| typedef struct STK{                                                                            |019| .       int l,w;                                                                               |020| }STK;                                                                                          |021| STK S[5001];                                                                                   |022|                                                                                                |023| //*=======================*Main Program*=======================*//                             |024| using namespace std;                                                                           |025|                                                                                                |026| int cmp(const void*a,const void* b){                                                           |027| .       struct STK* c=(STK*)a;                                                                 |028| .       struct STK* d=(STK*)b;                                                                 |029| .       return c->l==d->l?c->w-d->w:c->l-d->l;                                                 |030| }                                                                                              |031| int main(){                                                                                    |032| .       //freopen("input","r",stdin);                                                          |033| .       cin>>T;                                                                                |034| .       while(T--){                                                                            |035| .       .       cin>>n;                                                                        |036| .       .       for(int i=0;i
        
         >S[i].l>>S[i].w;                                                         |038| .       .       qsort(S,n,sizeof(STK),cmp);//排序（先按l，l相同再按w）              |039| .       .       int sum=0;                                                                     |040| .       .       memset(mark,0,sizeof(mark));//初始化标记为false                          |041| .       .       for(int i=0;i
         
          =w){                                                 |048| .       .       .       .         mark[j]=1;                                                   |049| .       .       .       .         w=S[j].w;//这句很重要                                   |050| .       .       .       .       }                                                              |051| .       .       .       }                                                                      |052| .       .       .       //mark[i]=1;//这句没必要                                          |053| .       .       }                                                                              |054| .       .       cout<
          
           <