就是成都现场赛的C题,我能想到的数据都过了,可提交WA,可能第一次DP考虑不全,但是全的话要多26倍,更大的可能是第二次DP有错.向各位站友求教.先谢过了.^__^
以下是代码,囧.我太菜了,被这题虐死了.-___________-
#include <stdio.h>
#include <string.h>
int dp1[105][105][27];
  int dp2[105][105];
  int dp3[105][105];
  int dp4[105][105];
int main()
{
char a[105];
  char b[105];
  
  int n,i,j,k,r,i1,j1,k1,t,min,min1,min2,min3;
  int tag;
while (gets(a+1)) 
  {
      gets(b+1);
      n=strlen(a+1);
      memset(dp1,0,sizeof(dp1));
      for (i=1;i<=n;i++)
      {
          for(i1=1;i1<=26;i1++)
          {
              if(b[i]-96==i1)
                  dp1[i][i][i1]=0;
              else
                dp1[i][i][i1]=1;
          }
      }
      for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
                dp2[i][j]=10000;
      for(i=1;i<=n;i++)
          dp2[i][i]=0;
      for (r = 2; r <= n; r++)
        for ( i = 1; i <= n - r+1; i++) 
        {
            j=i+r-1;
            for(i1=1;i1<=26;i1++)
            {
                dp1[i][j][i1] = dp1[i+1][j][i1]+((b[i]-96==i1)?0:1);
            }
            for (k=i; k<j;k++) 
            {
                for(k1=1;k1<=26;k1++)
                { 
                t = dp2[i][k]+dp2[k+1][j];
                if(dp1[i][k][k1]!=dp2[i][k])
                    t++;
                      if(dp1[k+1][j][k1]!=dp2[k+1][j])
                    t++;
                    if(t<dp2[i][j])
                    dp2[i][j]=t;
              if (t < dp1[i][j][k1]) 
              {
                dp1[i][j][k1] = t;
                
              }
                
            }
            }
      }
        memset(dp4,0,sizeof(dp4));
        for(i=1;i<=n;i++)
            for(j=i;j<=n;j++)
            {
            if(a[j]==b[j])
                dp4[i][j]=1;
            else
                break;
            }
/*for(k=1,j=1;k<=n;k++)
{
    if(d1[k])
    {
        if(k>j)
        {
        min+=dp2[j][k-1];        
        }
        j=k;
    }
}
min+=dp2[j][k-1];*/
    memset(dp3,0,sizeof(dp3));
        for(i=1;i<=n;i++)
            if(a[i]==b[i])
                dp3[i][i]=0;
            else
                dp3[i][i]=1;
      for ( r = 2; r <= n; r++)
        for ( i = 1; i <= n - r+1; i++) {
            
            j=i+r-1;
            if(!dp4[i][j])
            {
                
                t =dp2[i][j];
                
        for(i1=i+1;i1<=j;i1++)
                if(a[i1]!=a[i1-1])
                {
                    t++;
                    goto b1;
                }

    if(dp1[i][j][a[i]-96]!=dp2[i][j])
                t++;
b1:                    dp3[i][j]=t;
                       if(a[j]==b[j])
						   if(dp3[i][j]>dp3[i][j-1])
                      dp3[i][j]=dp3[i][j-1]; 
                       
            }
        

        else
        {
              dp3[i][j]=0;   
        }
            for ( k = i+1; k <j; k++) {
                t = (dp4[i][k]?0:dp2[i][k]) +(dp4[k+1][j]?0:dp2[k+1][j]);
                if(!dp4[i][k])
                {
                    for(i1=i+1;i1<=k;i1++)
                if(a[i1]!=a[i1-1])
                {
                    t++;
                    goto b2;
                }
                if(dp1[i][k][a[i]-96]!=dp2[i][k])
                t++;
                }
b2:                if(!dp4[k+1][j])
                {
        for(i1=k+2;i1<=j;i1++)
                if(a[i1]!=a[i1-1])
                {
                    t++;
                    goto b3;
                }
                if(dp1[k+1][j][a[j]-96]!=dp2[k+1][j])
                t++;
            }
      b3:        if (t < dp3[i][j]) {
                dp3[i][j] = t;
                }
                
              }
			if(dp3[i][j-1]+1<dp3[i][j])
				dp3[i][j]=dp3[i][j-1]+1;
            
            }
/*for(i=1;i<=n;i++)
{
            for(j=1;j<=n;j++)
            printf("%d ",dp3[i][j]);    
          printf("\n");
}
for(i=1;i<=n;i++)
{
            for(j=1;j<=n;j++)
            printf("%d ",dp2[i][j]);    
          printf("\n");
}
for(i=1;i<=n;i++)
{
            for(j=1;j<=n;j++)
            printf("%d ",dp4[i][j]);    
          printf("\n");
}*/
        printf("%d\n",dp3[1][n]);
  }
  return 0;
}

• Re:HDU的2476求助(成都现场赛C题) (33) timeloop 2009-01-21 18:04:00