http://cplusoj.com/d/senior/p/SS231107B
It is found that the reverse operation will modify a bunch of numbers, but what if we only focus on some of them?
Assume we have constructed
[
1
,
i
?
1
]
[1,i-1]
[1,i?1], we now try to construct
[
i
,
n
]
[i,n]
[i,n], our operable range is
[
i
?
1
,
n
]
[i-1,n]
[i?1,n]
hypothesis
i
i
i in
p
o
s
i
pos_i
posi?, we actually want to be in a long-term
n
?
i
+
1
n-i+1
The upper position of the sequence n?i + 1
p
o
s
i
?
i
+
2
pos_i-i + 2
posii + 2 moved to position 2, this thing is very dp. So we set
d
p
(
x
,
y
)
dp(x,y)
dp(x,y) means the length is
x
x
x, from
y
y
Minimum number of steps to move y to 2.
Note that this dp does not necessarily require an optimal strategy, which means we can make greedy decisions. We can enumerate whether the last grid is selected, or how many are selected. Then we greedily hope
y
y
y moves forward each time. (Moving backward may also be feasible, but we are looking for the optimal solution within the range, so it is not necessary)
Then this will still be slightly exceeded, so we can consider continuing to improve greedy. We can maintain pointers from front to back
x
x
x and back-to-front pointers
y
y
y, take the optimal shift.
#include<bits/stdc + + .h>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stdout, ##__VA_ARGS__)
#else
#define debug(...) void(0)
#endif
//#define int long long
inline int read(){<!-- -->int x=0,f=1;char ch=getchar(); while(ch<'0'||
ch>'9'){<!-- -->if(ch=='-')f=-1;ch=getchar();}while(ch>='0' & amp; & amp;ch<='9'){<!-- -->
x=(x<<1) + (x<<3) + (ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
#define first
#define se second
//srand(time(0));
#define N 3010
//#define M
//#define mo
int rev[13][100010];
void revese(int n, int l) {<!-- -->
for(int i=0; i<n; + + i) rev[l][i]=((rev[l][i>>1]>>1)|((i & amp;1)<< l-1));
}
void Min(int & amp;a, int b) {<!-- -->
a=min(a, b);
}
struct Fe {<!-- -->
int x, lstx, lsty, opx, opy;
Fe operator = (const int a) {<!-- -->
x=a; return (*this);
}
}f[N][N], g[N][N];
Fe Min(Fe a, Fe b) {<!-- -->
return a.x<b.x? a : b;
}
int n, m, i, j, k, T;
int a[N], pos[N];
vector<pair<int, int> >G;
void init() {<!-- -->
int x, y, l, t;
for(x=0; x<N; + + x) for(y=0; y<N; + + y) f[x][y].x=g[x][y].x=1e9;
for(x=3; x<=n; + + x) {<!-- -->
for(y=2; y<x; + + y) {<!-- -->
f[x][y]=f[x-1][y];
if(y==2) f[x][y]=0;
for(k=1; (1<<k)<=x; + + k) {<!-- -->
l=x-(1<<k) + 1;
if(l>=y) continue;
t=y-l;
// debug("[%d][%d] %d %d\\
", x, y, k, t);
if(rev[k][t]<t & amp; & amp; f[x][l + rev[k][t]].x + 1<f[x][y].x) {<! -- -->
f[x][y].x=f[x][l + rev[k][t]].x + 1;
f[x][y].lstx=x; f[x][y].lsty=l + rev[k][t];
f[x][y].opx=l; f[x][y].opy=k;
}
}
// debug("f[%d][%d]=%d\\
", x, y, f[x][y].x);
}
}
for(x=3; x<=n; + + x) {<!-- -->
for(y=x-1; y>=2; --y) {<!-- -->
g[x][y]=g[x-1][y-1];
if(y==x-1) g[x][y]=0;
for(k=1; (1<<k)<=x; + + k) {<!-- -->
if((1<<k)<y) continue;
t=y-1;
if(rev[k][t]>t & amp; & amp; g[x][rev[k][t] + 1].x + 1<g[x][y].x) {<! -- -->
debug(">>> %d || %d %d 【】 %d\\
", k, rev[k][t], t, g[x][rev[k][t] + 1].x);
g[x][y].x=g[x][rev[k][t] + 1].x + 1;
g[x][y].lstx=x; g[x][y].lsty=rev[k][t] + 1;
g[x][y].opx=x; g[x][y].opy=k;
}
}
debug("g[%d %d] = %d\\
", x, y, g[x][y].x);
}
}
}
void work(int l, int k) {<!-- -->
for(int i=0; i<(1<<k); + + i)
if(i<rev[k][i]) swap(a[i + l], a[rev[k][i] + l]);
}
void remake_pos() {<!-- -->
for(int i=1; i<=n; + + i) pos[a[i]]=i;
}
signed main()
{<!-- -->
freopen("butterfly.in", "r", stdin);
freopen("butterfly.out", "w", stdout);
#ifdef LOCAL
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
// T=read();
// while(T--) {<!-- -->
//
// }
\t
n=read(); m=read();
for(i=0; i<=12; + + i) revese(1<<i, i);
for(i=1; i<=n; + + i) a[i]=read();
remake_pos();
init();
int x, y;
x=2; y=n-1;
while(x<y) {<!-- -->
if(pos[x]==x) {<!-- --> + + x; continue; }
if(pos[y]==y) {<!-- --> --y; continue; }
int len=y-x + 1;
int s1=f[len + 2][pos[x]-x + 2].x;
int s2=g[len + 2][pos[y]-x + 2].x;
debug("=== %d %d\\
", s1, s2);
if(s1<s2) {<!-- -->
debug("oper 1\\
");
auto t=f[len + 2][pos[x]-x + 2];
while(t.opx) {<!-- -->
G.pb({<!-- -->t.opx + x-2, t.opy}); work(t.opx + x-2, t.opy);
t=f[t.lstx][t.lsty];
}
+ + x;
}
else {<!-- -->
debug("oper 2\\
");
auto t=g[len + 2][pos[y]-x + 2];
while(t.opx) {<!-- -->
G.pb({<!-- -->y + 2-t.opx, t.opy}); work(y + 2-t.opx, t.opy);
t=g[t.lstx][t.lsty];
}
--y;
}
remake_pos();
for(int i=1; i<=n; + + i) debug("%d ", a[i]); debug("\\
");
}
for(int i=1; i<=n; + + i) debug("%d ", a[i]); debug("\\
");
printf("%d\\
", G.size());
for(auto t : G) printf("%d %d\\
", t.fi, t.se);
return 0;
}