POJ 1850 Code文字列難易度:1

タイトル:
1厳格に昇順されたアルファベット文字列の場合、0以外の復号を出力できます.そうしないと、出力0を復号できません.
2文字列復号化は、これまでのすべてのアルファベット順が文字列の数+1より小さい値の増分原則に従う.

#include <iostream>



using namespace std;

char ans[11];

int a[10];

int c[27][27];

long long f[10];

void generc(){//     

    for(int i=1;i<27;i++)c[i][0]=c[i][i]=1;

    for(int i=2;i<27;i++){

        for(int j=1;j<27;j++){

            c[i][j]=c[i-1][j]+c[i-1][j-1];

        }

    }

}

void generf(){//        len ,        len            

    f[0]=0;

    for(int i=1;i<10;i++){

        f[i]=f[i-1]+c[26][i];//   i              ,      i       

    }

}



long long calc(){

    int len=0;//    ,   cstring

    for(len=0;len<10;len++){

        if(ans[len]==0)break;

        a[len]=ans[len]-'a';//      ,    

    }



    int former=0;//       +1,               ,     ,   a[-1]=-1;  a[0] 0('a')  

    long long res=0;//    

    res+=f[len-1];//        len          

    for(int i=0;i<len;i++){//     i       a[i]    

        for(int j=former;j<a[i];j++){//

            res+=c[25-j][len-1-i];//25-j        len-1-i                 ,           

        }

        former=a[i]+1;

    }

    return res+1;//              +1

}

bool check(){//        ,         ,wa   

    int fl=true;

    int len=0;

    char former='a'-1;

    for(len=0;len<10;len++){

        if(ans[len]==0)break;

        if(ans[len]<=former){

            fl=false;

            break;

        }

        former=ans[len];

    }

    if(len==0)return false;//    

    return fl;

}

int main(){

    generc();

    generf();

    cin>>ans;//      ,wa   

    if(check())cout<<calc()<<endl;

    else cout<<0<<endl;

    return 0;



}

　　
この問題は水だが,私が題意を読まないことを反映しているので,私が書いたのもよくないので,次は大神の題解を探しに行きます.
解法2題解後の新しいアイデアを見て、dp、でも悲しいのはformerの存在を忘れたことです//16 ms

#include <iostream>

using namespace std;

char ans[11];

int a[10];

int len;

long long memo[11][27];//memo[i][j] i      j         (j=26          'X')

//memo[i][j]   <i  &&       j           

void setmemo(){

    //memo[1][0]=0;//a             

    for(int i=1;i<27;i++)memo[1][i]=memo[1][i-1]+1;

    for(int i=2;i<11;i++){

        //memo[i][0]=0;

        for(int j=1;j<26;j++){

            memo[i][j]=memo[i][j-1]+memo[i-1][26]-memo[i-1][j];//        j   

        }

        memo[i][26]=memo[i][25];//    >1          z

    }

}

long long calc(){

    long long ans=0;



    for(int i=0;i<len;i++){

        ans+=memo[len-i][a[i]];

        if(i)ans-=memo[len-i][a[i-1]+1];

        ans+=memo[i][26];

    }

    return ans+1;

}

bool check(){

    bool fl=true;

    char former='a'-1;

    for(len=0;len<10;len++){

        if(ans[len]==0)break;

        if(ans[len]<=former){

            fl=false;

            break;

        }

        a[len]=ans[len]-'a';

        former=ans[len];

    }

    if(len==0)return false;

    return fl;

}

int main(){

    setmemo();

    while(cin>>ans){

    if(check())cout<<calc()<<endl;

    else cout<<0<<endl;}

    return 0;

}