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