• <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 閱讀(275) 評論(0)  編輯 收藏 引用 所屬分類: Topcoder 、Algorithm
            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)

             

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

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

            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);  
                    }

             

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

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

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

            最終全集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];
                    }
            中文字幕人妻色偷偷久久| 日本WV一本一道久久香蕉| a高清免费毛片久久| 亚洲天堂久久精品| 久久中文字幕精品| 国产精品久久久久无码av| 久久性精品| 国内精品人妻无码久久久影院| 99久久国产主播综合精品| 国产一区二区久久久| 久久精品国产99国产精品澳门 | 日韩精品久久无码中文字幕| 久久精品无码专区免费东京热| 久久久青草久久久青草| 国产精品99久久久精品无码| 精品久久久久久亚洲精品| 四虎影视久久久免费观看| 狠狠干狠狠久久| 久久久久久伊人高潮影院| 久久久久国产成人精品亚洲午夜| 亚洲精品国精品久久99热一| 色婷婷噜噜久久国产精品12p| 久久国产精品99久久久久久老狼 | 久久99精品久久久久久久不卡| 久久精品这里只有精99品| 香蕉久久夜色精品国产小说| 亚洲国产精品成人久久| 国产精品久久久久久久久久影院| 久久精品?ⅴ无码中文字幕| 久久精品国产99久久久| 精品国产99久久久久久麻豆| 久久久中文字幕日本| 久久伊人精品青青草原日本| 99久久精品国产一区二区蜜芽| 国产精品久久波多野结衣| 亚洲乱码中文字幕久久孕妇黑人| 思思久久好好热精品国产| 人妻无码αv中文字幕久久琪琪布| 久久精品国产一区二区| 国产叼嘿久久精品久久| 久久久久国产视频电影|