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. }

Full text and comments »

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

why problem C is PE at test 5(Codeforces Beta Round #26 (Codeforces format))?
By weiqi, 16 years ago, In English
code:
#include <vector> 
#include <list> 
#include <map> 
#include <set> 
#include <deque> 
#include <stack> 
#include <bitset> 
#include <algorithm> 
#include <functional> 
#include <numeric> 
#include <utility> 
#include <sstream> 
#include <iostream> 
#include <iomanip> 
#include <cstdio> 
#include <cmath> 
#include <cstdlib> 
#include <ctime> 
#include <queue> 
#include <string.h> 
using namespace std; 
#define mod 1000 
char flag[101][101]; 
int main() 
{ 
    int n,m,a,b,c,nn,mm,i,j,k; 
    scanf("%d %d %d %d %d",&n,&m,&a,&b,&c); 
    if(n*m%2==1)printf("IMPOSSIBLE\n"); 
    else 
    { 
        nn=n;mm=m; 
        if(n%2==1) 
        { 
            for(i=0;i<m;i+=2) 
            { 
                flag[n-1][i]=1; 
                flag[n-1][i+1]=1; 
                a--; 
            } 
            if(a<0) 
            { 
                printf("IMPOSSIBLE\n"); 
                return 0; 
            } 
            n--; 
        } 
        if(m%2==1) 
        { 
            for(i=0;i<n;i+=2) 
            { 
                flag[i][m-1]=2; 
                flag[i+1][m-1]=2; 
                b--; 
            } 
            if(b<0) 
            { 
                printf("IMPOSSIBLE\n"); 
                return 0; 
            } 
            m--; 
        } 
        i=0;j=0; 
        while(i<n) 
        { 
            char t = (char)('a' + ((i/2) % 2) * 2 + (j/2) % 2);  
            if(c>0) 
            { 
                c--; 
                flag[i][j]=t; 
                flag[i][j+1]=t; 
                flag[i+1][j]=t; 
                flag[i+1][j+1]=t; 
                j+=2; 
                if(j>=m) 
                { 
                    j=0; 
                    i+=2; 
                } 
            } 
            else if(b>1) 
            { 
                b-=2; 
                flag[i][j]=t; 
                flag[i+1][j]=t; 
                flag[i][j+1]=t+5; 
                flag[i+1][j+1]=t+5; 
                j+=2; 
                if(j>=m) 
                { 
                    j=0; 
                    i+=2; 
                } 
            } 
            else if(a>1) 
            { 
                a-=2; 
                flag[i][j]=t; 
                flag[i][j+1]=t; 
                flag[i+1][j]=t+5; 
                flag[i+1][j+1]=t+5; 
                j+=2; 
                if(j>=m) 
                { 
                    j=0; 
                    i+=2; 
                } 
            } 
            else break; 
        } 
        if(i>=n) 
        { 
            for(i=0;i<nn;i++) 
            { 
                for(j=0;j<mm;j++) 
                { 
                    printf("%c",flag[i][j]); 
                } 
                printf("\n"); 
            } 
        } 
        else 
        { 
            printf("IMPOSSIBLE\n"); 
        } 
    } 
    return 0; 
}

Full text and comments »

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