• <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 閱讀(276) 評論(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)

             

            要求最好的得分,要遍歷所有的排列方式顯然不可能。如果轉化問題為依次放置每個選手到每一個位置,那么只要求出剩下選手排列中使得得分最大的就可以了,可以想到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];
                    }
            久久影院亚洲一区| 久久久久国产一级毛片高清板| 伊人色综合久久天天人守人婷| 香蕉99久久国产综合精品宅男自 | 国产精品免费久久| 欧美大战日韩91综合一区婷婷久久青草| 久久五月精品中文字幕| 中文字幕乱码人妻无码久久| 99精品久久久久久久婷婷| 国产精品久久久久…| 国产精品日韩深夜福利久久| 麻豆av久久av盛宴av| 久久精品国内一区二区三区| 精品久久久久久无码国产| 久久精品卫校国产小美女| 久久久久一区二区三区| 思思久久精品在热线热| 91久久精品无码一区二区毛片| 性做久久久久久久久老女人| 精品蜜臀久久久久99网站| 国产69精品久久久久APP下载 | 日韩美女18网站久久精品| 久久国产精品77777| 伊人久久大香线蕉综合热线| 91精品无码久久久久久五月天| 亚洲国产精品无码久久久蜜芽 | 国内精品久久久久久久亚洲| 日本强好片久久久久久AAA| 伊人色综合久久天天| 久久久久国产精品熟女影院| 深夜久久AAAAA级毛片免费看 | 久久久婷婷五月亚洲97号色| 久久综合亚洲鲁鲁五月天| 久久99久久无码毛片一区二区| 97r久久精品国产99国产精| 久久久久亚洲av无码专区导航| 伊人久久大香线蕉综合网站| 久久久久一本毛久久久| 久久精品亚洲欧美日韩久久| 国产免费久久久久久无码| 国产亚州精品女人久久久久久 |