• <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>

            superman

            聚精會(huì)神搞建設(shè) 一心一意謀發(fā)展
            posts - 190, comments - 17, trackbacks - 0, articles - 0
               :: 首頁(yè) :: 新隨筆 :: 聯(lián)系 :: 聚合  :: 管理

            ZOJ 1102 - Phylogenetic Trees Inherited

            Posted on 2008-04-06 11:13 superman 閱讀(430) 評(píng)論(0)  編輯 收藏 引用 所屬分類: ZOJ

            Official Solution:

            Problem G: Phylogenetic Trees Inherited

            The first thing to observe is that the different positions in every sequence are independent of each other. This reduces the tree of sequences to a tree of amino acids. At the root of the tree, or for that matter of any sub-tree, there may be many possible amino acids leading to optimal costs. Suppose, you have calculated for two sub-trees Tl and Tr the sets of amino-acids leading to optimal costs Al and Ar. Adjacent sub-trees Tl and Tr have as their father the node T. Now you want to find the set of amino-acids A that you can mark T with, leading to optimal costs for T.

            There are two cases: if the intersection of Al with Ar is non-empty, define A as just this intersection, otherwise define A to be the union of Al and Ar. To see why this is true, observe the extra costs you get, when you assemble T from Tl and Tr. In the first case, you have 0 extra costs when you take an amino-acid from the intersection, but 1 or 2 extra costs when you do not. In the second case, you have 1 extra costs when you take an amino-acid from the union, but 2 extra-costs when you do not. Now, you may want to assemble T not from Tl and Tr but from some other sub-optimal trees. As you can easily verify, this leads to sub-optimal costs for T as well.

            This reasoning is carried over straightforwardly to an induction proof and leads to a dynamic programming solution. Since the amino-acids are upper-case letters, you can represent sets of amino-acids as ints. The set operations you need are then easily performed as bitwise and respectively or. Whenever you do a union operation, your costs increase by 1.

            Another, more straight-forward solution is to calculate for each node of the tree the optimal costs for every amino acid the node can be marked with. This is done by trying every possible combination of amino acids for the two sub-trees, assuming their optimal costs have already been calculated. Since this solution might turn out to be too inefficient, it can be improved upon by observing that a father node always can be marked with either the left or the right son's amino-acid - there is no need to take an amino acid that differs from both.

            Judges' test data was constructed from a test-case with a few long sequences, a test-case with many short sequences, a test-case where every possible pair of amino-acids occured, and 100 random-generated test-cases where length and number of sequences are geometrically distributed. The total number of test-cases is 110. Since there may be multiple correct answers for the test cases, a special verification program was written by slightly modifying the judges' solution.


             1 /* Accepted 1102 C++ 00:00.56 1040K */
             2 #include <string>
             3 #include <iostream>
             4 
             5 using namespace std;
             6 
             7 int main()
             8 {
             9     int n, l;
            10     while((cin >> n >> l) && n && l)
            11     {
            12         int heap[2048], cost = 0;
            13         string seq[1024];
            14         
            15         for(int i = 0; i < n; i++)
            16             cin >> seq[i];
            17         
            18         for(int i = 0; i < l; i++)
            19         {
            20             for(int k = 0; k < n; k++)
            21                 heap[n + k] = 1 << (seq[k][i] - 'A');
            22             for(int k = n - 1; k >= 1; k--)
            23                 if((heap[k] = heap[2 * k] & heap[2 * k + 1]) == 0)
            24                 {
            25                     cost++;
            26                     heap[k] = heap[2 * k] | heap[2 * k + 1];
            27                 }
            28             char c = 'A';
            29             while(heap[1>>= 1)
            30                 c++;
            31             cout << c;
            32         }
            33         cout << ' ' << cost << endl;
            34     }
            35     
            36     return 0;
            37 }
            38 
            亚洲乱码中文字幕久久孕妇黑人 | 久久国产乱子精品免费女| 麻豆精品久久久久久久99蜜桃 | 久久国产精品久久精品国产| 99久久精品无码一区二区毛片 | 香蕉久久久久久狠狠色| 波多野结衣AV无码久久一区| 国产欧美一区二区久久| 久久人人爽人人澡人人高潮AV | 国产成人精品久久二区二区| 91秦先生久久久久久久| 国产亚洲美女精品久久久2020| 久久r热这里有精品视频| 久久久受www免费人成| 热re99久久精品国99热| 色婷婷噜噜久久国产精品12p| 激情伊人五月天久久综合| 日本久久中文字幕| 9191精品国产免费久久| 久久精品水蜜桃av综合天堂| 亚洲人成网站999久久久综合 | 久久国产精品久久| 亚洲日韩中文无码久久| 久久综合九色欧美综合狠狠| 国产一区二区三区久久精品| 伊人久久久AV老熟妇色| 亚洲精品久久久www| 理论片午午伦夜理片久久| 欧美精品一本久久男人的天堂| 99久久久国产精品免费无卡顿| 国产精品99久久久久久宅男小说| 精品久久久无码中文字幕天天| 一本大道久久a久久精品综合| 久久精品水蜜桃av综合天堂| 亚洲国产精品无码久久一区二区 | 久久99亚洲网美利坚合众国| 久久毛片一区二区| 久久久久久曰本AV免费免费| 色狠狠久久综合网| 亚洲色大成网站WWW久久九九| 亚洲午夜久久久影院|