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