0%

Project2501[HAOI2006]数字序列工作报告

摘要:无

P2501 [HAOI2006]数字序列

题面

题目分析

第一问:做补集转化,最大化不用操作的数,可以发现两个不用操作的数之间的关系是a[j]-a[i]>j-i,即两个数之间至少要隔a[j]-a[i]位,移项就可以得到a[j]-j>a[i]-i,设b[i]=a[i]-i,求出序列b中的最长不降子序列即可

第二问:a最长上升即b最长不降,现在已经得出了序列b的最长不降子序列,考虑这个子序列中两个相邻数之间中间相隔的数怎么操作,可以反证出这两个位置之间一定没有介于两个位置上的数之间的数,然后考虑将之间的数划分成梯度,每个数要下降或者上升到梯度上去,发现如果下降的数多于上升的数,把梯度移到右边高的梯度会更优,反之亦然,就可以发现不断这么操作之后,一定只存在两个梯度,一个是等于区左端点,一个等于右端点,枚举梯度交换的地方,用前缀和算出需要操作的次数就可以了

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include "iostream"
#include "cstring"
#include "cstdlib"
#include "cctype"
#include "cstdio"
#include "cctype"
#include "iomanip"
#include "algorithm"
#include "queue"
#include "map"
#include "stack"
#include "deque"
#include "time.h"
#include "set"
#include "cmath"
#define debug(x) printf("debug:%lld\n",x)
#define lxl long long
#define R register
#define INF 0x3f3f3f3f
const lxl maxn=35010;
lxl n,len;
lxl b[maxn],lis[maxn],f[maxn],SumL[maxn],SumR[maxn],ttt[maxn];
std::vector<lxl>v[maxn];
inline lxl read()
{
char c=getchar();
lxl f=1,x=0;
for(;!isdigit(c);c=getchar())(c=='-')&&(f=-1);
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
return f*x;
}
int main(void)
{
memset(f,0x3f,sizeof(f)),f[0]=0;
n=read();
for(R int i(1);i<=n;++i)b[i]=read()-i;
b[n+1]=INF,b[0]=-INF;
for(R int i(1);i<=n+1;++i)
{
if(b[i]>=lis[len])++len,lis[len]=b[i],v[len].push_back(i),ttt[i]=len;
else
{
lxl pos=std::upper_bound(lis+1,lis+1+len,b[i])-lis;
// debug(pos),debug(lis[pos]);
lis[pos]=std::min(lis[pos],b[i]);
v[pos].push_back(i);
ttt[i]=pos;
}
// debug(len);
}
v[0].push_back(0);
printf("%lld\n",n-len+1);
for(R int i(1);i<=n+1;++i)
{
// debug(ttt[i]);
for(R int j(0);j<v[ttt[i]-1].size();++j)
{
lxl to=v[ttt[i]-1][j];
if(to>i||b[to]>b[i])continue;
SumL[to]=0;
for(R int k(to+1);k<=i-1;++k)SumL[k]=SumL[k-1]+abs(b[k]-b[to]);
SumR[i-1]=0;
for(R int k(i-2);k>=to;--k)SumR[k]=SumR[k+1]+abs(b[k+1]-b[i]);
for(R int k(to);k<=i-1;++k)f[i]=std::min(f[i],f[to]+SumR[k]+SumL[k]);
}
}
printf("%lld\n",f[n+1]);
return 0;
}