3689 浮云

赛后a题都是浮云，就是不明白，之前怎么就连这么简单的题都不敢写。这种dp有什么，建个状态转移图不久ok了，什么时候我才不悲剧！！！！！！！！！！！

#include <iostream>

#include <cstring>

using namespace std;

struct Node{

    int next[26];

    double p;

} node[10];

struct Char_pro{

    char c;

    double p;

} cp[26];

char word[11];

int n,m,len;

inline bool ok(int s1,int s2,int a){

    if(word[s1--]!=char('a'+a)) return false;

    for(; s1>=0; --s1,--s2){

        if(word[s1]!=word[s2])

            return false;

    }

    return true;

}

void build_ac(){

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

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

            for(int k=i; k>=0; --k){

                if(ok(k,i-1,j)){

                    node[i].next[j]=k+1;

                    break;

                }

            }

        }

    }

}

int main(){

    char tmp;

    while(scanf("%d %d",&n,&m)){

        scanf("%c",&tmp);

        if(n==0&&m==0){

            break;

        }

        memset(node,0,sizeof(node));

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

            scanf("%c %lf/n",&cp[i].c,&cp[i].p);

        }

        scanf("%s",word);

    //    printf("%s/n",word);

        len=strlen(word);

        build_ac();

        node[0].p=1.0;

        double tmpp[10];

        double ans=0.0;

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

            memset(tmpp,0,sizeof(tmpp));

            for(int j=0; j<n; ++j){

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

                    if(node[k].next[cp[j].c-'a']==len) ans+=node[k].p*cp[j].p;

                    tmpp[node[k].next[cp[j].c-'a']]+=node[k].p*cp[j].p;

                    }

                }

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

                node[k].p=tmpp[k];

            }

        }

        printf("%.2lf%%/n",ans*100);

        fflush(stdout);

    }

}