• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            pku3691 DNA repair 自動機+DP

            題意:
            給出一個DNA序列,和若干病毒DNA片段,問最少修改DNA的次數使得DNA序列中不包含病毒

            解法:
            首先構造DFA(再次犯了和福州現場賽一樣的錯誤,沒有+結束標記狀態的轉移。。。。WA了N久),然后就是在狀態機上的DP了
            令dp[i]][j]為當前在自動機第i個節點上時suffix(j)成為合法子串需要修改的最少次數。下面狀態轉移就簡單了。。(這種狀態轉移通過方程和難描述,大家看程序吧,我寫的很清楚地~)

            代碼:
              1import java.io.*;
              2import java.util.Arrays;
              3public class Main {
              4
              5    /**
              6     * @param args
              7     */

              8    static class node
              9    {
             10        node nxt[]=new node[4];
             11        int id=0;
             12        boolean end=false;
             13        node pre=null;
             14    }

             15    static node head=null,buffer[]=new node[1500],q[]=new node[1500];
             16    static int s=-1,e=-1,dp[][]=new int[1005][1005];
             17    static int c=0;
             18    static String str;
             19    static void clear(node pos)
             20    {
             21        Arrays.fill(pos.nxt, null);
             22        pos.end=false;
             23        pos.pre=null;
             24    }

             25    static void insert(String str)
             26    {
             27        node p=head;
             28        for(int i=0;i<str.length();i++)
             29        {
             30            int nxt=0;
             31            switch(str.charAt(i))
             32            {
             33                case 'A':nxt=0;break;
             34                case 'C':nxt=1;break;
             35                case 'G':nxt=2;break;
             36                case 'T':nxt=3;break;
             37            }
            ;
             38            if(p.nxt[nxt]==null)
             39            {
             40                clear(buffer[c]);
             41                p.nxt[nxt]=buffer[c++];
             42            }

             43            p=p.nxt[nxt];
             44        }

             45        p.end=true;
             46    }

             47    static void makeper()
             48    {
             49        s=e=-1;
             50        node p=head;
             51        for(int i=0;i<4;i++)
             52            if(p.nxt[i]==null)
             53                p.nxt[i]=p;
             54            else
             55            {
             56                p.nxt[i].pre=p;
             57                q[++e]=p.nxt[i];
             58            }

             59        while(s!=e)
             60        {
             61            p=q[++s];
             62            for(int i=0;i<4;i++)
             63            {
             64                node pre=p.pre;
             65                while(pre.nxt[i]==null) pre=pre.pre;
             66                if(p.nxt[i]==null)
             67                    p.nxt[i]=pre.nxt[i];
             68                else
             69                {
             70                    p.nxt[i].pre=pre.nxt[i];
             71                    p.nxt[i].end=(p.nxt[i].end||pre.nxt[i].end);
             72                    q[++e]=p.nxt[i];
             73                }

             74            }

             75        }

             76    }

             77    static int solve(int pos,node p)
             78    {
             79        if(p.end) return 2000;
             80        else if(pos==str.length()) return 0;
             81        else if(dp[p.id][pos]!=-1return dp[p.id][pos];
             82        else
             83        {
             84            dp[p.id][pos]=0;
             85            switch(str.charAt(pos))
             86            {
             87            case 'A':
             88                dp[p.id][pos]+=Math.min(Math.min(solve(pos+1,p.nxt[0]),solve(pos+1,p.nxt[1])+1),Math.min(solve(pos+1,p.nxt[2])+1,solve(pos+1,p.nxt[3])+1));
             89                break;
             90            case 'C':
             91                dp[p.id][pos]+=Math.min(Math.min(solve(pos+1,p.nxt[0])+1,solve(pos+1,p.nxt[1])),Math.min(solve(pos+1,p.nxt[2])+1,solve(pos+1,p.nxt[3])+1));
             92                break;
             93            case 'G':
             94                dp[p.id][pos]+=Math.min(Math.min(solve(pos+1,p.nxt[0])+1,solve(pos+1,p.nxt[1])+1),Math.min(solve(pos+1,p.nxt[2]),solve(pos+1,p.nxt[3])+1));
             95                break;
             96            case 'T':
             97                dp[p.id][pos]+=Math.min(Math.min(solve(pos+1,p.nxt[0])+1,solve(pos+1,p.nxt[1])+1),Math.min(solve(pos+1,p.nxt[2])+1,solve(pos+1,p.nxt[3])));
             98                break;
             99            }
            ;
            100            return dp[p.id][pos];
            101
            102        }

            103    }

            104    public static void main(String[] args) throws IOException{
            105        BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
            106        int count=1;
            107        for(int i=0;i<buffer.length;i++)
            108        {
            109            buffer[i]=new node();
            110            buffer[i].id=i;
            111        }

            112        while(true)
            113        {
            114            int num=Integer.parseInt(in.readLine());
            115            if(num==0break;
            116            c=1;
            117            clear(buffer[0]);
            118            head=buffer[0];
            119            while((num--)!=0)
            120              insert(in.readLine());
            121            for(int i=0;i<c;i++)
            122                Arrays.fill(dp[i],-1);
            123            makeper();
            124            str=in.readLine();
            125            int ans=solve(0,head);
            126            if(ans>=2000) System.out.println("Case "+count+++": -1");
            127            else System.out.println("Case "+count+++""+ans);
            128        }

            129
            130    }

            131
            132}

            133

            posted on 2011-01-12 13:21 yzhw 閱讀(248) 評論(0)  編輯 收藏 引用 所屬分類: DPstring algorithm

            <2010年12月>
            2829301234
            567891011
            12131415161718
            19202122232425
            2627282930311
            2345678

            導航

            統計

            公告

            統計系統

            留言簿(1)

            隨筆分類(227)

            文章分類(2)

            OJ

            最新隨筆

            搜索

            積分與排名

            最新評論

            閱讀排行榜

            久久亚洲精品人成综合网| 久久青青色综合| 久久国产免费观看精品| 久久国产乱子精品免费女| 国产福利电影一区二区三区久久老子无码午夜伦不 | 欧洲精品久久久av无码电影| 大伊人青草狠狠久久| 精品久久久久国产免费| 亚洲精品蜜桃久久久久久| 久久精品九九亚洲精品天堂| 亚洲精品WWW久久久久久| 99久久综合狠狠综合久久止| 日韩AV毛片精品久久久| 99国产精品久久| 亚洲国产美女精品久久久久∴| 久久免费国产精品一区二区| 久久午夜免费视频| 99久久国产主播综合精品 | 韩国三级大全久久网站| 久久精品女人天堂AV麻| 91精品国产91久久久久福利 | 无码人妻精品一区二区三区久久久 | 久久综合九色欧美综合狠狠| 色偷偷88888欧美精品久久久| 欧美成人免费观看久久| 国产成人无码精品久久久久免费 | 亚洲第一永久AV网站久久精品男人的天堂AV| 久久99精品国产麻豆宅宅| 人人狠狠综合88综合久久| 狠狠色丁香久久综合婷婷| 久久精品亚洲AV久久久无码| 久久久久亚洲AV无码专区桃色| 99久久精品免费| 99久久精品国产综合一区| 2021久久精品国产99国产精品| 无码人妻精品一区二区三区久久久 | 久久亚洲欧洲国产综合| 久久久精品人妻无码专区不卡| 国产精品免费久久| 久久久精品人妻无码专区不卡| 久久久久久毛片免费看|