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

            TCCC-05-1000pt-

            Posted on 2009-11-23 15:29 rikisand 閱讀(274) 評(píng)論(0)  編輯 收藏 引用 所屬分類: TopcoderAlgorithm
            Problem Statement

            Just before a chess match between two teams, each team's coach secretly determines an ordering of his team's players. The first players in each team then get to play against each other, the second players in each team play against each other, etc. The team with the most wins will win the match.

            You are the coach for one of the teams, and you have somehow managed to find out the order of the players in the other team. Based on that, you want to order your players so that your team's expected score is maximized to your advantage. The expected score of a single game can be calculated by the following formula (which is directly derived from how the international chess rating system works):

            EA = 1 / (1 + 10 (RB - RA)/400)
            
            EB = 1 / (1 + 10 (RA - RB)/400)
            

            where RA and RB are the ratings of player A and B, and EA and EB are the expected scores for each player. For instance, if RA is 2432 and RB is 2611, the expected score for player A is 1 / (1 + 10179/400) = 0.263005239459. The expected score for a team is the sum of the expected scores for the players in that team.

            To make things a bit more complicated, the players in a team must be ordered such that a player with rating x plays before all players with rating strictly less than x - lim, where lim is a given non-negative integer. For example, if lim is 100, a player with rating 2437 must play before a player with rating 2336 but not necessarily before a player with rating 2337.

            Create a class ChessMatch containing the method bestExpectedScore which takes a vector <int> teamA, the ratings of your players (in no particular order); a vector <int> teamB, the ratings of your opponent's players in the order they will play; and an int lim, the limit determining how freely you can order your players. You can assume that your opponent's players will be ordered in accordance with lim. The method should return a double, your team's expected score if you order your players optimally.

            Definition

            Class:
            ChessMatch

            Method:
            bestExpectedScore

            Parameters:
            vector <int>, vector <int>, int

            Returns:
            double

            Method signature:
            double bestExpectedScore(vector <int> teamA, vector <int> teamB, int lim)

            (be sure your method is public)

             

            要求最好的得分,要遍歷所有的排列方式顯然不可能。如果轉(zhuǎn)化問(wèn)題為依次放置每個(gè)選手到每一個(gè)位置,那么只要求出剩下選手排列中使得得分最大的就可以了,可以想到dp方法的最有子問(wèn)題定義。

            用每一位記錄當(dāng)前的選手分配情況,如果為0,則已經(jīng)分配,如果為1,則還未分配。pos來(lái)記錄當(dāng)前要分配的位置。對(duì)于每一個(gè)子集,考慮每一個(gè)為1的也就是未分配的選手使位于pos位置,然后check 是否滿足在他之后的球員(也就是剩下的是1的位)是否滿足條件的不等式,滿足則更新當(dāng)前分配的最優(yōu)成績(jī)。最終 2^N-1 的成績(jī)即為所求。

            Code Snippet
            #define REP(i, n) for (int i = 0; i < (n); ++i)
            #define two(X) (1<<(X))
            #define contain(S,X) ((S&two(X))>0)
            #define eps 1e-9
            double p[20][20];
            int N;
            double memo[1<<20];
            int lim;VI A;
            bool check(int now,int pos){
                REP(i,N)if(now&two(i)){
                    if(A[pos]+lim<A[i])return false;
                }
                return true;
            }
            double solve(int now,int pos){
                if(now==0) return 0;
                if(memo[now]>-eps)return memo[now];
                REP(i,N) if(contain(now,i)&&check(now^two(i),i)){
                     double tmp=p[i][pos]+solve(now^two(i),pos+1);
                     if(tmp>memo[now]+eps) memo[now]=tmp;
                }
                return memo[now];
            }

            class ChessMatch
            {
                    public:
                    double bestExpectedScore(vector <int> tA, vector <int> tB, int _lim)
                    {
                        N=tA.size(); lim=_lim;A=tA;
                        REP(i,N)REP(j,N)  p[i][j]=1.0/(1.0+pow(10.0,double(tB[j]-tA[i])/400.0));
                        REP(i,1<<N)memo[i]=-1;
                        return solve(two(N)-1,0);  
                    }

             

            上面的方法使用遞歸,下面是使用遞推的程序。即從子集出發(fā)最終到達(dá)2^n-1的思路。在這里把A隊(duì)伍先從大到小排序。在每一個(gè)子集記錄每一個(gè)未分配選手的得分和要分配的位置。

            程序中思路為:依次從子集中選取一個(gè)選手作為第bits-1個(gè)選手,也就是說(shuō)子集中剩下的元素要放在這個(gè)選手前面,由于選手從小到大遍歷,只需要遍歷到s[j]<=s[bits-1]+lim 為止,也就說(shuō)滿足這個(gè)子集中最小的選手+lim >=選中的 即可,然后更新當(dāng)前子集的得分

            注釋中思路為: 依次從子集選取一個(gè)選手作為當(dāng)前子集中的第一個(gè)元素,也就是整體的第n-bits個(gè)元素,這次從大到小遍歷,這樣只需要保證,位于子集第一個(gè)的元素+lim>=子集中最大的元素(s[0]),即可,然后更新當(dāng)前子集得分

            最終全集2^n-1的即為所求

            Code Snippet
            class ChessMatch
            {
                    public:
                    double bestExpectedScore(vector <int> ta, vector <int> tb, int _lim)
                    {
                            int n=ta.size();a=ta;lim=_lim;N=n;
                            sort(ta.begin(),ta.end(),greater<int>());int s[32],pos[32];
                            REP(i,n)REP(j,n)p[i][j]=1./(1.+pow(10.,double(tb[j]-ta[i])/400.));
                            REP(mask,1<<n){
                                int bits=0;
                                dp[mask]=0.;
                                if(!mask)continue;
                                REP(i,n) if(contain(mask,i)){
                                    s[bits]=ta[i];pos[bits++]=i;
                                }
                                //for (int j = 0 ; j < bits  && s[j] + lim >= s[0]; j++){
                                //    if(dp[mask] < p[pos[j]][n-bits]+dp[mask^two(pos[j])])
                                //        dp[mask]= p[pos[j]][n-bits]+dp[mask^two(pos[j])] ;
                                
                                for (int j = bits-1; j >= 0 && s[j] <= s[bits-1] + lim; j--){
                                if(    dp[mask] <  p[pos[j]][bits-1] + dp[mask & ~(1 << pos[j])] )
                                  dp[mask] = p[pos[j]][bits-1] + dp[mask & ~(1 << pos[j])];
                                }
                            }
                            return dp[two(n)-1];
                    }
            精品久久久无码中文字幕天天| 四虎国产精品成人免费久久| 国产91久久综合| 久久亚洲精品人成综合网| 久久笫一福利免费导航| 热久久国产欧美一区二区精品| 国产一区二区精品久久岳| 久久精品国产亚洲AV香蕉| 久久精品国产亚洲AV麻豆网站 | 亚洲AV日韩AV天堂久久| 国产精品一区二区久久精品涩爱| 青青草国产97免久久费观看| 久久精品无码一区二区三区日韩| 国产精品成人精品久久久| 91精品观看91久久久久久| 久久www免费人成看国产片| 久久久网中文字幕| 一级做a爰片久久毛片看看| 伊色综合久久之综合久久| 伊人久久大香线蕉综合影院首页| 伊人久久精品无码av一区| 99久久免费国产特黄| 亚洲精品国产成人99久久| 欧美久久天天综合香蕉伊| 久久久久亚洲AV无码专区首JN | 久久精品国产72国产精福利| 欧美与黑人午夜性猛交久久久 | 青青草原精品99久久精品66| 精品免费久久久久久久| 精品99久久aaa一级毛片| 久久精品国产欧美日韩99热| 久久免费的精品国产V∧| 91精品国产91久久久久久蜜臀| 亚洲国产成人精品久久久国产成人一区二区三区综 | 久久久久人妻一区二区三区vr| 韩国免费A级毛片久久| 久久精品成人| 久久久久久人妻无码| 久久久久成人精品无码| 久久久久久无码Av成人影院| 中文字幕精品久久久久人妻|