問題
http://community.topcoder.com/stat?c=problem_statement&pm=11115&rd=14426
解き方
配列の数が５０個なのですべての組み合わせは求められないので
順番が決まるか、貪欲法で求められるはず。
左から数を調べていくとすると、その数は昇順である方がよいので、
その点から連続するDの数だけ確保しておけば、そのうち最小の数を
とってもよいことがわかる。
よって、そのようにして左側から数を決定していく。l
コード
class PermutationSignature {
public:
vector<int> reconstruct(string signature) {
int n=signature.size()+1;
int used[n+1];
memset(used,0,sizeof(used));
vector<int> ans;
FORE(i,0,n){
int cnt=0;
FORE(j,i,signature.size()){
if(signature[j]!='D')break;
cnt++;
}
int x=1;
while(used[x])x++;
while(cnt>0){
x++;
if(used[x])continue;
cnt--;
}
ans.push_back(x);
used[x]=1;
}
return ans;
}
};
public:
vector<int> reconstruct(string signature) {
int n=signature.size()+1;
int used[n+1];
memset(used,0,sizeof(used));
vector<int> ans;
FORE(i,0,n){
int cnt=0;
FORE(j,i,signature.size()){
if(signature[j]!='D')break;
cnt++;
}
int x=1;
while(used[x])x++;
while(cnt>0){
x++;
if(used[x])continue;
cnt--;
}
ans.push_back(x);
used[x]=1;
}
return ans;
}
};