問題
http://community.topcoder.com/stat?c=problem_statement&pm=8590&rd=12174
解き方
全探索可能。
配列の状態を持つのでdpではなくmapを利用してDFSで解く。
コード
map<vector<int>,double> m;
int n;
class RandomSort {
public:
double rec(vector<int> p){
if(m.find(p)!=m.end())return m[p];
int cnt=0;
FORE(i,0,n)FORE(j,i+1,n)if(p[i]>p[j])cnt++;
if(cnt==0)return m[p]=0;
double ret=0;
FORE(i,0,n)FORE(j,i+1,n){
if(p[i]>p[j]){
swap(p[i],p[j]);
ret+=rec(p)+1;
swap(p[i],p[j]);
}
}
return m[p]=ret/cnt;
}
double getExpected(vector<int> permutation) {
m.clear();
n=permutation.size();
return rec(permutation);
}
};
int n;
class RandomSort {
public:
double rec(vector<int> p){
if(m.find(p)!=m.end())return m[p];
int cnt=0;
FORE(i,0,n)FORE(j,i+1,n)if(p[i]>p[j])cnt++;
if(cnt==0)return m[p]=0;
double ret=0;
FORE(i,0,n)FORE(j,i+1,n){
if(p[i]>p[j]){
swap(p[i],p[j]);
ret+=rec(p)+1;
swap(p[i],p[j]);
}
}
return m[p]=ret/cnt;
}
double getExpected(vector<int> permutation) {
m.clear();
n=permutation.size();
return rec(permutation);
}
};
Share this
Related Posts
SRM 668 DIV1 Easy - PaintTheRoom
問題
https://community.topcoder.com/stat?c=problem_statement&pm=13846&rd=16548
解き方
K=1の場合はどのようなR,Cでも達成でき- SRM 551 DIV1 Easy - ColorfulChocolates
問題
http://community.topcoder.com/stat?c=problem_statement&pm=12137&rd=15173
解き方
各アルファベットごとに最大の連続数を考え、最
- SRM 539 DIV1 Easy - Over9000Rocks
問題
http://community.topcoder.com/stat?c=problem_statement&pm=11855&rd=14731
解き方
９０００以上となる数をすべて保存しては間に合
- SRM 526.5 DIV1 Easy - MagicCandy
問題
http://community.topcoder.com/stat?c=problem_statement&pm=11706&rd=14762
解き方
普通に計算していては間に合わない。
例えば２