Untitled
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879
#include<bits/stdc++.h>
using namespace std;
map<vector<int>,int> mp;
int rep(vector<int> &a){
if(a.empty()){return 0;}
if(mp.find(a)!=mp.end()){
return mp[a];
}
int res=0;
for(int i=1;i<a.size();i++){
if(a[i-1]==i){
vector<int> und;
for(int j=0;j<a.size();j++){
if(j==i-1 || j==i){continue;}
und.push_back(a[j]);
}
res=max(res,rep(und)+1);
}
}
mp[a]=res;
return res;
}
int pow(int a,int b){int i,r=1;for(i=1;i<=b;i++){r*=a;}return r;}
int greedy(vector<int> a){
int res=0;
while(true){
bool fin=true;
for(int i=((int)a.size())-1;i>=1;i--){
if(a[i-1]==i){
vector<int> na;
for(int j=0;j<a.size();j++){
if(j==i-1 || j==i){continue;}
na.push_back(a[j]);
}
res++;
a=na;
fin=false;
break;
}
}
if(fin){break;}
}
return res;
}
int main(){
std::random_device seed_gen;
std::mt19937_64 engine(seed_gen());
int fail=0;
while(true){
if(mp.size()>2e6){mp.clear();}
int n=1+(engine()%30);
vector<int> a(n);
for(auto &nx : a){
nx=rand()%n+1;
}
int ok=rep(a);
int gd=greedy(a);
if(ok!=gd){
cout << a.size() << "\n";
for(auto &nx : a){
cout << nx << " ";
}cout << "\n";
cout << ok << " " << gd << "\n";
fail++;
if(fail>=5){break;}
}
}
return 0;
}
Cpp
INFO