• <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>
            算法學社
            記錄難忘的征途
            posts - 141,comments - 220,trackbacks - 0
            吐槽:
               無力吐槽了,450pt怎么那么難。。。

            250pt
               題目意思是,有N(N<=50)個數,每個數的可變范圍是[max(N-X,1),N+X]。讓這個數列嚴格遞增的最小X是多殺?
            算法分析:
               二分枚舉答案然后貪心判定。每個數都盡可能的小。
             1 #include<vector>
             2 #include<iostream>
             3 using namespace std;
             4 class KingdomAndTrees{
             5     public : int minLevel(vector <int> num){
             6         int n = num.size();
             7         int l = 0, r = 1000000000;
             8         while(l<r){
             9             int mid = l+r >>1;
            10             int pre = 0, flag = 1;
            11         //    cout<<l<<" "<<r<<" "<<mid<<endl;
            12             for(int i=0;i<n;i++){
            13                 if(num[i] + mid <= pre){ flag = 0; break; }
            14                 pre = max(pre+1, num[i] - mid);
            15             //    if(mid == 5) cout<< pre<<" ";
            16             }
            17             if(flag) r = mid; else l = mid+1;
            18         }
            19         return l;
            20     }
            21 };

            450pt
               有兩個N<50個面的骰子,每個面的數字是1-X的唯一某個數。第一個骰子有些面是0。現在兩個骰子同時投擲,請你把第一個骰子某些為0的面寫上一些唯一的1-X的數字,讓第一個骰子的勝率盡可能接近0.5。

            算法分析:
               等同于求,有一大堆數[1,X]。有N個空格,讓你求在某些空格上寫一些數,最后可以勝利的所有可能。
               背包模型,動規求解。DP[i][j][k],表示前i個骰子,填入前j個空格,是否可能贏k次。用0-1背包的寫法,可以省一唯空間。

             1 #include<vector>
             2 #include<algorithm>
             3 #include<iostream>
             4 using namespace std;
             5 bool dp[55][2555];
             6 class KingdomAndDice{
             7 public : double newFairness(vector <int> fD, vector <int> sD, int X){
             8     int now = 0, len = 0, n = sD.size();
             9     for(int i=0;i<n; i++){
            10         len += fD[i] == 0;
            11         for(int j=0; j<n; j++)
            12             now += fD[i] > sD[j];
            13     }
            14     sort(sD.begin(), sD.end());
            15     int mx = n*n;
            16     for(int i=0;i<=len; i++) dp[i][now] = 1;
            17     for(int i=0;i<n;i++){
            18         int l = sD[i] + 1;
            19         int r = i== n-1 ? X : sD[i+1] - 1;
            20         int cnt = r - l + 1;
            21         for(int j=0; j<n; j++) if(fD[j] >=l && fD[j] <= r) cnt --;
            22         cnt = min(cnt, len);
            23         for(int j=0; j< cnt; j++)
            24             for(int k = len-1;k >=0; k--)
            25                 for(int p = 0; p <= mx; p++)
            26                     if(dp[k][p] && p + i + 1 <= mx){
            27                         dp[k+1][p + i + 1] = 1;
            28                     }
            29     }
            30     int  m = abs(n*n ), ans = now;
            31     for(int p = 0; p <=mx; p++){
            32         for(int i=0; i<=len; i++)    {
            33             if(dp[i][p] && abs(n*n-p*2) < m){
            34                 ans = p; m = abs(n*n-p*2);
            35             }
            36         }
            37     }
            38     return 1.0*ans/mx;
            39 }
            40 };

            posted on 2012-07-04 12:05 西月弦 閱讀(431) 評論(0)  編輯 收藏 引用
            久久精品三级视频| 2020久久精品亚洲热综合一本| 久久国产乱子伦免费精品| 久久99国产精品一区二区| 久久久久国产精品麻豆AR影院| 伊人精品久久久久7777| 精品久久8x国产免费观看| 亚洲嫩草影院久久精品| 狠狠色丁香婷婷久久综合| 97久久国产亚洲精品超碰热| 久久午夜福利电影| 久久亚洲国产午夜精品理论片| 欧美麻豆久久久久久中文| 99久久精品午夜一区二区| 国产精品一区二区久久精品涩爱| 精品午夜久久福利大片| 热99RE久久精品这里都是精品免费| 2021精品国产综合久久| 久久99久国产麻精品66| 久久中文字幕视频、最近更新| 久久精品国产亚洲AV高清热| 久久天天婷婷五月俺也去| 久久av高潮av无码av喷吹| 国产亚洲精品自在久久| 亚洲午夜久久久影院伊人| 国产69精品久久久久APP下载 | 99久久综合国产精品免费| 伊人色综合久久| 久久人人妻人人爽人人爽| 欧美日韩精品久久免费| 精品久久久久久久久久久久久久久 | 久久久久99精品成人片欧美| 久久综合九色综合网站| 久久这里只有精品首页| 亚洲国产一成久久精品国产成人综合 | 久久精品成人影院| 99久久人人爽亚洲精品美女| 久久青青草原精品影院| 国产精品美女久久久m| 久久成人影院精品777| 99久久精品国产综合一区 |