weiqi's blog

Who can help me at contest 66 problem C?
By weiqi, 16 years ago, In English
I know it is DP.but I wrong ans at test 6;
My dp transfer equation is 

i is the length of name s， j  is current position ,r is represent that r  characters have been replace. h is the the latter characters .
This is the code.
  1. int rec[30][30]={0};
  2. int dp[101][30][101];
  3. bool flag[101][30][101];
  4. int main()
  5. {
  6.         int i,j,r,h,c;
  7.         char str[1001],k,n,ac[5],ab[5];
  8.         scanf("%s %d",&str,&k);
  9.         scanf("%d",&n);
  10.         //gets(&ac);
  11.         for(i=0;i<n;i++)
  12.         {
  13.                 scanf("%s %s %d",ab,ac,&c);
  14.                 rec[ab[0]-'a'][ac[0]-'a']=c;
  15.         }
  16.         int len=strlen(str);
  17.         memset(flag,0,sizeof(flag));
  18.         for(i=0;i<26;i++)
  19.         {
  20.                 if(i==str[len-1]-'a')
  21.                 {
  22.                         dp[len-1][i][0]=0;
  23.                         flag[len-1][i][0]=1;
  24.                 }
  25.                 else
  26.                 {
  27.                         dp[len-1][i][1]=0;
  28.                         flag[len-1][i][1]=1;
  29.                 }
  30.         }
  31.         if(len==1)
  32.         {
  33.                 printf("0\n");
  34.                 return 0;
  35.         }
  36.         int ans=0;
  37.         bool si=0;
  38.         for(i=len-2;i>=0;i--)
  39.         {
  40.                 for(j=0;j<26;j++)
  41.                 {
  42.                         if(j==str[i]-'a')
  43.                         {
  44.                                 for(h=0;h<=k;h++)
  45.                                 {
  46.                                         for(r=0;r<26;r++)
  47.                                         {
  48.                                                 if(flag[i+1][r][h]==0)continue;
  49.                                                 if(flag[i][j][h]==0)    
  50.                                                 {
  51.                                                         dp[i][j][h]=dp[i+1][r][h]+rec[j][r];
  52.                                                         flag[i][j][h]=1;
  53.                                                 }
  54.                                                 else dp[i][j][h]=max(dp[i][j][h],dp[i+1][r][h]+rec[j][r]);
  55.                                         }
  56.                                 }
  57.                         }
  58.                         else
  59.                         {
  60.                                 for(h=1;h<=k;h++)
  61.                                 {
  62.                                         for(r=0;r<26;r++)
  63.                                         {
  64.                                                 if(flag[i+1][r][h-1]==0)continue;
  65.                                                 if(flag[i][j][h]==0)
  66.                                                 {
  67.                                                         dp[i][j][h]=dp[i+1][r][h-1]+rec[j][r];
  68.                                                         flag[i][j][h]=1;
  69.                                                 }
  70.                                                 else
  71.                                                         dp[i][j][h]=max(dp[i][j][h],dp[i+1][r][h-1]+rec[j][r]);
  72.                                         }
  73.                                 }
  74.                         }
  75.                 }
  76.         }
  77.         ans=0;
  78.         si=0;
  79.         for(i=0;i<26;i++)
  80.         {
  81.                 for(j=0;j<=k;j++)
  82.                 {
  83.                         if(flag[0][i][j]==1)
  84.                         {
  85.                                 if(si==0)
  86.                                 {
  87.                                         si=1;
  88.                                         ans=dp[0][i][j];
  89.                                 }
  90.                                 else ans=max(ans,dp[0][i][j]);
  91.                         }
  92.                 }
  93.         }
  94.         printf("%d\n",ans);
  95.         return 0;
  96. }

  • Vote: I like it
  • -7
  • Vote: I do not like it

16 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it
How about go debug your solution? For starters, maybe find the first cell with different value than you think it should have. And find out why.
→ Reply
16 years ago, hide # |
← Rev. 2  
Vote: I like it +1 Vote: I do not like it
If you click on your submission ID in "my submissions" tab you can see the test you've failed at. It can help a bit.
→ Reply