音游家的谱面(Hardversion)

（本题和Easy version的区别仅在数据范围不同）

牛牛最近在玩一款叫做牛特斯的下落式音游，下落式音游是一种音乐节拍类游戏，在屏幕上平行分布若干条轨道，音符在这些轨道上移动。

当音符与屏幕底部的判定线重合时点击音符即可命中。对于有 ${N}$ 条轨道的音游被称之为是一个 ${N}$ Key音游，例如常见的4 Key音游，5 Key音游，8 Key音游。

在一轮游戏中共有 ${M}$ 个音符，对于每一个音符，都有两个属性 ${pos_i}$ 和 ${time_i}$ ， ${pos_i}$ 为正整数，表示音符下落时所属的轨道为 ${pos_i}$ ， ${time_i}$ 是一个实数，表示音符到达判定线的时间为 ${time_i}$ 毫秒，由于 ${time_i}$ 是一个实数，同时出现的音符被理解成间隔非常小的时间单位，所以允许音符同时出现。

游玩这类音游时，一般人会使用两只手，或者两只拇指，并且游戏开始时左手放在1号轨道，右手放在第 ${N}$ 号轨道。在第 ${i}$ 毫秒中（第 ${i}$ 毫秒中指 ${[i,i+1)}$ 这段时间区间，左闭右开），如果两只手分别放在 ${x}$ 和 ${y}$ 这两个位置上，那么理论上就可以命中在第i毫秒中轨道 ${x}$ 和 ${y}$ 上到达判定线的所有音符。（当然，如果你技术够好的话）

在每一毫秒末，两只手可以独立的各自进行移动，但是只能移动到它们相邻的轨道上。具体来讲，假设左右手在第 ${i}$ 毫秒中位于 ${x}$ 和 ${y}$ 这两个位置上，记为 ${(x,y)}$ 。那么在第 ${i}$ 毫秒末，共有9种不同的移动方案，即 ${(x-1,y-1),(x,y-1),(x+1,y-1),(x-1,y),(x,y),(x+1,y),(x-1,y+1),(x,y+1),(x+1,y+1)}$ 。

在音游中，有一些谱面由于过度反人类，不适合人类游玩而被称为是“粪谱”。
具体来讲，如果假设一开始左手在第 ${1}$ 号轨道，右手在第 ${N}$ 号轨道，双手各自独立的按照上述规则，每毫秒末移动一个单位。不存在任何一种方案可以在理论上全部命中的 ${M}$ 个音符，就称这个谱面是一个“粪谱”。

我们称最后一个音符，即第 ${M}$ 个音符到达判定线的时间为整个谱面的时长。

现在给你这 ${M}$ 个音符按照时间顺序的轨道坐标 ${pos_i}$ ，请你设计一个谱面时长最小的非“粪谱”谱面。
也就是说你需要给出这 ${M}$ 个音符到达判定线的时间 ${time_i}$ ，并且要求 $time_1 \leq time_2 \leq ... \leq time_M$ ， ${time_i}$ 可以为实数，但是为了避免一些不必要的精度问题，你只需要输出 $\left \lfloor time_i \right \rfloor$ 即可。

当然，符合条件的谱面不唯一，你只用输出任意一种符合题目要求的即可。

#include <bits/stdc++.h> using namespace std; #define fi first #define se second const int inf = 0x3f3f3f3f; const int maxn = 5e3+10; int n,m,f[maxn][maxn],a[maxn],pre[maxn][maxn],l[maxn],r[maxn]; typedef pair<int,int>p; p fl[maxn],fr[maxn],q[maxn]; void dfs(int fir,int sec) { if( fir==0 ) return; dfs( fir-1,pre[fir][sec] ); cout << f[fir][sec] << " "; } void solve() { int ans = inf, chu = 0; for(int i=1;i<=n;i++) { if( f[m][i]<ans ) ans = f[m][i],chu = i; if( f[m][i]<ans ) ans = f[m][i],chu = i; } dfs( m,chu ); } int main() { cin >> n >> m; for(int i=1;i<=m;i++) cin >> a[i]; memset( f,0x3f3f3f3f,sizeof f ); f[0][n] = 0, a[0] = 1; for(int i=1;i<=m;i++) { int lim = abs( a[i]-a[i-1] ); for(int j=1;j<=n;j++) l[j] = max(1,j-lim), r[j] = min( n,j+lim ); int head = 1, tail = 0, z = 1; for(int j=1;j<=n;j++)//上一次一只手为j,另一只手为a[i-1] { //按音符的手去按下一个音符,这是一个定值,只需要求出左右区间长度为lim的中f[i-1][j]的最小值即可 while( z<=r[j] ) { while( tail>=head && f[i-1][z]+lim<=q[tail].fi ) tail--; q[++tail] = p( f[i-1][z]+lim,z ); z++; } while( q[head].se<l[j] ) head++; f[i][j] = q[head].fi, pre[i][j] = q[head].se; } for(int j=0;j<=n+1;j++) fl[j] = fr[j] = p(inf,inf); for(int j=1;j<=n;j++)//可以更新的窗口[]递减 { lim = abs( j-a[i] );//递减 int le = max( 1,a[i-1]-lim ), re = min( n,a[i-1]+lim );//可更新窗口 fl[le] = min( fl[le],p( f[i-1][j]+lim,j ) ); fr[re] = min( fr[re],p( f[i-1][j]+lim,j ) ); } for(int j=1;j<=a[i-1];j++) fl[j] = min( fl[j],fl[j-1] );//往右边max for(int j=n;j>=a[i-1];j--) fr[j] = min( fr[j],fr[j+1] );//往左边取max for(int j=1;j<=a[i-1];j++) if( f[i][j]>fl[j].fi ) f[i][j] = fl[j].fi, pre[i][j] = fl[j].se; for(int j=a[i-1];j<=n;j++) if( f[i][j]>fr[j].fi ) f[i][j] = fr[j].fi, pre[i][j] = fr[j].se; } solve(); }

详情