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

            oyjpArt ACM/ICPC算法程序設計空間

            // I am new in programming, welcome to my blog
            I am oyjpart(alpc12, 四城)
            posts - 224, comments - 694, trackbacks - 0, articles - 6

            說幾道題目

            Posted on 2007-08-06 12:00 oyjpart 閱讀(1896) 評論(2)  編輯 收藏 引用 所屬分類: ACM/ICPC或其他比賽
            PKU 3371 Stake Your Claim
            這道題比較好的算法(而且我只能用這個過)就是把空缺的10個空位用3進制狀態壓縮表示(0代表沒放,1代表0號選手放的,2代表1號選手放的) 然后做記憶化搜索
            我開始用的是AB剪枝 始終TLE 后來腦袋不清醒 在AB剪枝的同時加DP結果變成WA,后來想到AB剪枝的時候棋盤局面和剪枝有關 故不能隨便DP
            不知哪位高人能給與指點解決這個問題
            下面是AB剪枝的大概流程,我們看到剪枝的時候返回值是跟sta(當前子局面中最優的)有關的,所以不能直接DP
             1
             2int search(int p, int sta) { //假定現在在計算S的子局面S2,sta則是S1的狀態值
             3    if(p == 0) { //假定S局面取小,如果S2比S1大 則無用 即只要S2的子局面有一個比STA大 S2就無用了 退出
             4        int now = -MAXINT; //S2局面取大 初始化為最小
             5        for( every possible action ) {
             6            //go this action;
             7            int next = search(1now);
             8            now = Max(nownext); 
             9            //cancel this cation
            10            if(now > sta) break; //S2的某個子局面出現了比sta還小的 退出
            11        }
            12        return now;
            13    } 
            14    else { //假定S局面取大,如果S2比S1小 則無用 即只要S2的子局面有一個比STA小 S2就無用了 退出
            15        int now = MAXINT;
            16        for( every possible action ) {
            17            //go this action;
            18            int next = search(1now);
            19            now = Min(nownext);
            20            //cancel this action
            21            if(now < sta) break; 
            22        }
            23        return now;
            24    }
            25}
            26

            TJU2879   Little Peter's Tower
            題目給你一個范圍內的積木 讓你隨即按次序得到T個積木 問你怎么堆才能堆得最高
            看到這題之后我一直以為題目要求我們找出一種最優策略
            但是苦于概率上的不確定性 沒有辦法找出
            沒想到其實不是這樣的 其實這是一個DP task。我們能夠得知的策略就是如果我們只有一個積木 那么我們必然會堆一個 不管他有多高 那么如果我們定義這樣的狀態:
            dp[top][time]  就可以得到下面的遞推式:
            dp[top][time] = 平均(max(dp[top][time-1], dp[k][time-1] + k); //k是高度
            于是程序寫出來倒是很短
            #include <iostream>
            using namespace std;

            double dp[120][120];

            #define Max(a, b) ((a) 
            > (b) ? (a) : (b))

            int main() {
                
            int R, H, T, i, j, k, r;
                
            int ntc;
                scanf(
            "%d"&ntc);
                
            while(ntc--) {
                    scanf(
            "%d %d %d"&R, &H, &T);
                    
            for(i = 1; i <= R; ++i) dp[0][i] = 0;
                    
            for(i = 1; i <= T; ++i) {
                        
            for(r = 1; r <= R; ++r) {
                            dp[i][r] 
            = dp[i-1][r] * (R-r) * H;
                            
            for(j = 1; j <= r; ++j)
                                
            for(k = 1; k <= H; ++k)
                                    dp[i][r] 
            += Max(dp[i-1][r], dp[i-1][j] + k);
                            dp[i][r] 
            /= R * H;
                        }
                    }
                    printf(
            "%.6lf\n", dp[T][R]);
                }
                return 
            0;
            }

            TJU2868   Fire Balloon
            一個很好的枚舉+DP的題目
            其實題目很好轉化成二分圖 但是數據范圍限制讓我們不得不另尋他法
            題目是一個有環圖,這個環在與:
            1.上下兩個點之間存在連接
            2.左右兩端連接起來了
            于是我們才與枚舉狀態 消除后效性做DP!
            首先把縱向的2個格子合并成一個大的狀態 這樣就退化成了一個環
            然后再在任意兩點之間枚舉兩點之間的連接情況 這樣就退化成了一條鏈
            終于可以開始DP了 呵呵


            PKU3265 Problem Solving
            初看真的非常像貪心 結果是DP 隱藏的真好 推薦

            TJU1037 Binary Search Tree I
            這道題我居然不是觀察數據 猜測 然后證明
            而是直接證明了才作。。。
            做法:排序所有的數
            如果一個數x的左邊那個數y和右邊的z那個數都比x先插入 那么它是葉子
            如果都比x后插入 也是葉子
            這樣證明:
            二叉樹的一個重要性質就是2分區間

            比如插入一個8
            就把分成了(-INF, 8] 和 [8, INF)
            如果一個數x的左邊那個數和右邊那個數都比x先插入
            那么他一定是葉子 為什么呢 如果他不是葉子
            比如他有左子樹 那么y一定在他的左子樹里面
            同理 可證明其他

            PKU3304 Segments
            又是一個要求轉化的題目
            題目給了一個映射共點的條件 幾乎沒什么用
            但是一旦你想到轉化成這一點出發的一條線會與所有線相交
            問題立刻轉化成了枚舉端點 確定這條線!

            Feedback

            # re: 說幾道題目  回復  更多評論   

            2007-08-16 11:04 by wywcgs
            TJU2879 Little Peter's Tower
            這道題本是IPSC 2007的題目
            這道題有兩個輸入文件
            其中第一個是小case,用你的方法是可以出的
            第二個是大case,你的方法出不來,需要再優化, 把for(k = 1; k <= H; ++k)這段干掉才行
            http://ipsc.ksp.sk/problems.php?arg_contest=ipsc2007
            你可以去下一下這題的數據,最后一道題。

            # re: 說幾道題目  回復  更多評論   

            2007-08-22 20:56 by oyjpart
            哦 wy大牛啊~
            欧美精品福利视频一区二区三区久久久精品 | 色综合久久中文字幕综合网| 久久成人影院精品777| 99久久精品国产高清一区二区| 国产国产成人精品久久| 久久国产成人| 亚洲国产另类久久久精品黑人| 久久精品国产亚洲AV无码偷窥| 国产精品久久久久久影院| 亚洲国产成人久久精品99 | 精品国产乱码久久久久久郑州公司| 久久亚洲精品中文字幕| 久久亚洲精品视频| 久久无码AV一区二区三区| 国产综合久久久久久鬼色| 久久www免费人成精品香蕉| 麻豆亚洲AV永久无码精品久久| 国产成人综合久久精品尤物| 久久精品人妻中文系列| 国産精品久久久久久久| 久久久久无码精品国产| 免费一级欧美大片久久网| 亚洲午夜精品久久久久久人妖| 77777亚洲午夜久久多喷| 91精品观看91久久久久久| 久久精品人人做人人爽97| 思思久久99热免费精品6| 婷婷综合久久狠狠色99h| 午夜人妻久久久久久久久| 思思久久好好热精品国产| 国产综合免费精品久久久| 日本一区精品久久久久影院| 久久久精品人妻一区二区三区蜜桃 | 久久人妻AV中文字幕| 久久久久无码精品国产app| 中文精品久久久久国产网址| 久久青青草原亚洲av无码app| yy6080久久| 色狠狠久久综合网| 亚洲精品第一综合99久久 | 一本一本久久aa综合精品|