首页 > ACM题库 > HDU-杭电 > hdu 2638 Greed is good[解题报告]C++
2014
02-12

hdu 2638 Greed is good[解题报告]C++

Greed is good

问题描述 :

As we all know Uncle CTW is a very greedy uncle,he likes collecting jewels.One day he gets a necklace with beautiful gems,he has a strange habit,that he only collects the contiguous gems with with same color.That means if he pick a red gem at first,and he will continue to pick only if the next gem is red,or he will stop.(That’s why people call him “Uncle.Strange”).
As it is a necklace,he must find somewhere to cut the necklace at the very begining,then select an end to pick until meet a different color gem,and do the same for the other end (which might not be of the same color as the gems collected before this).
There are only three kinds of gems,red(‘r’),pink(‘p’),and white(‘w’),and NOTICE that,because the white one could be painted,so it can be seen as either color.(See the sample for detail.)
Now he just want to know the maximum number of gems he can collect,could you tell him?

输入:

The first line contain an integer T,then T lines,each line with a string only contain r,p or w ,with length no more than 400.

输出:

The first line contain an integer T,then T lines,each line with a string only contain r,p or w ,with length no more than 400.

样例输入:

1
wwwpprwrprprrprprwrwwrpwrwrrp

样例输出:

11

Hint:
Consider two copies of the beads (kind of like being able to runaround the ends). The string of 11 is marked. 
wwwpprwrprprrprprwrwwrpwrwrrp wwwpprwrprprrprprwrwwrpwrwrrp
                       ****** *****

#include<stdio.h>
  #include<string.h>
  int main()
  {
     char nek[1000],bf[1000];
      int i,j,l,k;
      int as,bs,c1,c2;
      int ap,bp;
      int max;
     int t;
     
     while(scanf("%d",&t)!=EOF)
     {
         while(t--)
        {
            max=0;
           as=0;
            bs=1;
          scanf("%s",nek);
           strcpy(bf,nek);
            l=strlen(nek);
           while(bs<l)
             {
                ap=bp=0;
                c1=0;
                 c2=0;
                for(i=as;;i--)
                 {
                    if(i<0)
                    {
                        i=l-1;
                    }
                        if(nek[i]=='a')
                        break;
                    if(nek[i]=='w')
                        {
                            nek[i]='a';
                            c1++;
                       }
                        if(nek[i]=='p')
                        {
                            if(ap==0||ap==1)
                            {
                                 nek[i]='a';
                             ap=1;
                             c1++;
                             }else
                                 break;
                                 
                       }
                        if(nek[i]=='r')
                         {
                             if(ap==0||ap==2)
                             {
                                 nek[i]='a';
                             ap=2;
                             c1++;
                             }else
                             break;
                         }
                     
                           
                }
                 for(j=bs;;j++)
                 {
                     if(j==l)
                     {
                         j=0;
                     }
                         if(nek[j]=='a')
                        break;
                         if(nek[j]=='w')
                         {
                             nek[j]=='a';
                             c2++;
                         }
                       if(nek[j]=='p')
                         {
                             if(bp==0||bp==1)
                             {nek[j]=='a';
                            bp=1;
                             c2++;
                             }
                            else
                             break;                            
                         }
                        if(nek[j]=='r')
                         {
                             if(bp==0||bp==2)
                             {nek[j]=='a';
                             bp=2;
                             c2++;
                            }
                             else
                             break;
                        }
                   
 
 }
if(max<c1+c2)
{
max=c1+c2;
}
strcpy(nek,bf);
c1=c2=0;
ap=bp=0;
as++;
bs++;
}
c1=c2=0;
ap=bp=0;
as=bs=1;
for(i=l-1,j=0;i>j;i--,j++)
{
if(nek[i]=='w'&&as)
                    {
c1++;
}
if(nek[j]=='w'&&bs)
{
c2++;
}
if(nek[i]=='p'&&as)
{
if(ap==0||ap==1)
{
ap=1;
c1++;
}else
{as=0;
}
}
if(nek[j]=='p'&&bs)
{
if(bp==0||bp==1)
{
bp=1;
c2++;
}else
{
bs=0;
}
}
if(nek[i]=='r'&&as)
{
if(ap==0||ap==2)
{
ap=2;
c1++;
}else
as=0;
}
if(nek[j]=='r'&&bs)
{
                        if(bp==0||bp==2)
{
bp=2;
c2++;
}else
{
bs=0;
}
}
}
if(max<c1+c2)
{
max=c1+c2;
}
printf("%d\n",max);
}
}
}

 


  1. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。

  2. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。

  3. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。