[APIO2008 dna]动态规划、统计方案数

【题目】http://www.apio.olympiad.org/

【算法分析】

F[i,j,k]表示i..m这个后缀串中，s[i]==j，且有k个逆序的位置的方案数是多少。

然后Sum[i,j,k]表示F[i,j,0]+F[i,j,1]+….+F[i,j,k]

转移很简单，就不说了。

然后从1开始搞下来，利用Sum来从前面开始判定下来处理一下就好。

【CODE】

#include #include #include #include using namespace std;
typedef long long big;
big n,K,R;
int s[51111],ans[51111];
big F[51111][5][11],Sum[51111][5][11];

void input(){
     cin >> n >> K >> R;
     char c;
     for (int i=1;i<=n;i++){
         for (c=getchar();c==’n’ || c==’ ‘;c=getchar());
         switch (c){
                case ‘A’:
                     s[i]=1;
                     break;
                case ‘C’:
                     s[i]=2;
                     break;
                case ‘G’:
                     s[i]=3;
                     break;
                case ‘T’:
                     s[i]=4;
                     break;
                case ‘N’:
                     s[i]=0;
                     break;
         }
     }
     if (!s[n])
       for (int j=0;j<5;j++)
         F[n][j][0]=1;
     else
       F[n][s[n]][0]=1;
}

void dp(){
     int i,j,k,l;
     for (i=n-1;i>=1;i–)
       if (!s[i])
         for (j=1;j<5;j++)
           for (k=0;k             for (l=1;l<5;l++)
               if (l                 F[i][j][k+1]+=F[i+1][l][k];
               else
                 F[i][j][k]+=F[i+1][l][k];
       else{
         j=s[i];
           for (k=0;k             for (l=1;l<5;l++)
               if (l                 F[i][j][k+1]+=F[i+1][l][k];
               else
                 F[i][j][k]+=F[i+1][l][k];
       }
       for (i=1;i<=n;i++)
         for (j=1;j<5;j++)
           for (Sum[i][j][0]=F[i][j][0],k=1;k             Sum[i][j][k]=Sum[i][j][k-1]+F[i][j][k];
}

void output(){
     int i,j,k,kn=K;
     big ns,ss=0;
     for (i=1;i<=n;i++){
         kn–;
         for (j=1;j<5;j++){
             if (j==ans[i-1]) kn++;
             if (ss+Sum[i][j][kn]>=R) break;
             else ss+=Sum[i][j][kn];
         }
         ans[i]=j;
     }
//========================================================================
     char c;
     for (i=1;i<=n;i++){
         switch (ans[i]){
                case 1:c=’A’; break;
                case 2:c=’C’; break;
                case 3:c=’G’; break;
                case 4:c=’T’; break;
         }
         putchar(c);
     }
}

int main(){
    freopen("dna.in","r",stdin);
    freopen("dna.out","w",stdout);
    input();   
    dp();
    output();
}