No.145 yukiover - yukicoder
- y > u > k > i が降順なんでうまいこと再帰をすれば解けそうだなーと思ったけど、うまく再帰関数が書けなかった。
- 以下は他の人のコードを参照にした。こういうのも実装力なんだろうな。
const string target = "yuki@";
class Yukiover {
public:
vector<int> cnt;
bool dfs(int d) {
if (d == (int)target.size()+1)
return false;
char c = target[d];
if (cnt[c])
{
--cnt[c];
if (dfs(d+1))
return true;
++cnt[c];
}
++c;
for (; c <= 'z'; ++c)
{
if (cnt[c])
{
--cnt[c];
return true;
}
}
return false;
}
void solve(void) {
int N;
string S;
cin>>N>>S;
cnt.resize('z'+1,0);
for (auto c : S)
++cnt[c];
int n = 0;
while (dfs(0))
++n;
cout<<n<<endl;
}
};