問題
http://topcoder.bgcoder.com/print.php?id=1718
それぞれN人で構成される2つのチームが、団体戦でチェスの試合を行う。
試合はＮ回行われ、各試合は各チームのメンバ１対１で行われる。
各メンバは１試合しか出場できない。
試合については強い方のメンバのチームが２点加算され、同じ強さの場合は各チーム１点が加算される。
ここで自分のチームについては全メンバーの強さがわかっており、また相手の全メンバーの強さもわかっている。
このとき、自分のチームが得られる最も高いスコアを求める。
解き方
まずは各チームの強さを昇順にソートする。
自分のチームは弱い方から選んでいき、
相手の最も強いメンバに勝てるとき→そのメンバと対戦してスコア＋２
相手の最も弱いメンバに勝てるとき→そのメンバと対戦してスコア＋２
がもっともよい戦術であることがわかる。
ただし、上記のどれとも一致しない場合は
相手の最も強いメンバと弱いメンバ、どちらと対戦して良いかはその場で判断できない。
そのため、この２通りについてｄｐを回して高い方のスコアを採用すればよい。
ｄｐは６０＾３であるため十分に間に合う。
コード
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
int n,dp[60][60][60];
vector<int> us,them;
class ChessMatchup {
public:
int f(int pos,int left,int right){
if(pos==n)return 0;
if(dp[pos][left][right]!=-1)return dp[pos][left][right];
int ret=0;
if(us[pos]>them[right]){
ret=2+f(pos+1,left,right-1);
}
else if(us[pos]>them[left]){
ret=2+f(pos+1,left+1,right);
}
else{
ret=max((us[pos]==them[right])+f(pos+1,left,right-1),(us[pos]==them[left])+f(pos+1,left+1,right));
}
return dp[pos][left][right]=ret;
}
int maximumScore(vector<int> us_, vector<int> them_) {
us=us_;
them=them_;
n=us_.size();
sort(all(us));
sort(all(them));
memset(dp,-1,sizeof(dp));
return f(0,0,them.size()-1);
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
int n,dp[60][60][60];
vector<int> us,them;
class ChessMatchup {
public:
int f(int pos,int left,int right){
if(pos==n)return 0;
if(dp[pos][left][right]!=-1)return dp[pos][left][right];
int ret=0;
if(us[pos]>them[right]){
ret=2+f(pos+1,left,right-1);
}
else if(us[pos]>them[left]){
ret=2+f(pos+1,left+1,right);
}
else{
ret=max((us[pos]==them[right])+f(pos+1,left,right-1),(us[pos]==them[left])+f(pos+1,left+1,right));
}
return dp[pos][left][right]=ret;
}
int maximumScore(vector<int> us_, vector<int> them_) {
us=us_;
them=them_;
n=us_.size();
sort(all(us));
sort(all(them));
memset(dp,-1,sizeof(dp));
return f(0,0,them.size()-1);
}
};