首页 > 代码库 > 【BZOJ】1049: [HAOI2006]数字序列（lis+特殊的技巧）
【BZOJ】1049: [HAOI2006]数字序列（lis+特殊的技巧）
http://www.lydsy.com/JudgeOnline/problem.php?id=1049
又是一题神题啊。orz
首先第一个问很容易看出
f[i]=min{f[j]+1, a[i]-a[j]>=i-j}
设b[i]=a[i]-i
得
f[i]=min{f[j]+1, b[i]>=b[j]}
然后就是lis的log算法。。。。
第二个问，好神！！！
首先发现，如果有b[i]>=b[j]且f[i]==f[j]+1时，区间[j, i]中的点一定都是大于b[i]或者小于b[j]，很显然吧。。
而我们要将[j, i]的点变成合法序列一定是存在一个点t，使得[j, t]变成b[j]，[t+1, i]变成b[i]。（在原序列中就变成了a[j], a[j+1]=a[j]+1, a[j+2]=a[j]+2...这样）
如何证明？不会QAQ
试着证明一下：考虑最优点t，假设b[t]不变成b[j]，而是变成b‘[t]>b[j]，且b‘[t]<b[i]。那么因为原b[t]<b[j]或者b[t]>b[i]，显然费用为b‘[t]-b[t]>b[j]-b[t]（当b[t]<b[j]时）b[t]-b‘[t]>b[t]-b[i]（当b[t]>b[i]时），得出b[j]<b‘[t]<b[i]没有b‘[t]=b[j]或=b[i]优，即证。
那么这样搞是n^3的，，，，，，，，，，，，，，
先试着搞成n^2。考虑当前转移点为i
我们首先找出离i最远的j，b[i]>=b[j]且f[i]==f[j]+1，那么所有的合法点都包含在区间[j, i]中。
考虑从i向左枚举至j，当前在k，此时假设现在将所有[k+1, i-1]的点全部变为b[i]，那么当k是合法点时，我们需要得到最小值。
因为现在[k+1, i-1]全都是变成了b[i]，那么假设要将其中的点变成b[j]，显然：如果原b[x]>b[i]，那么费用还需要+(b[i]-b[j])，如果原b[x]<b[i]，那么费用就需要-(b[i]-b[j])。假设[k, i]中最优点t，[k+1, t]有y个比b[i]大的点，z个比b[i]小的点，那么需要变化的费用为：
sum-(b[i]-b[k])*z+(b[i]-b[k])*y=sum-(b[i]-b[k])*(z-y)，而区间[j, i]中所有合法k显然是b[k]单调不降的，所以b[i]-b[k]在减小，所以目标变成最大化(z-y)。
所以考虑前缀和找出最大的差就行了。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
那么问题变成n^2...
然后题目说。。。随机数据。。。。。。。。。。。。水过。
（还有注意一点是，如何快速找到j点，那么我们在lis时向所有转移点连边，然后快速找到即可，否则复杂度会更大）
#include <cstdio>#include <cstring>#include <cmath>#include <string>#include <iostream>#include <algorithm>#include <queue>#include <set>#include <map>using namespace std;typedef long long ll;#define rep(i, n) for(int i=0; i<(n); ++i)#define for1(i,a,n) for(int i=(a);i<=(n);++i)#define for2(i,a,n) for(int i=(a);i<(n);++i)#define for3(i,a,n) for(int i=(a);i>=(n);--i)#define for4(i,a,n) for(int i=(a);i>(n);--i)#define CC(i,a) memset(i,a,sizeof(i))#define read(a) a=getint()#define print(a) printf("%d", a)#define dbg(x) cout << (#x) << " = " << (x) << endl#define error(x) (!(x)?puts("error"):0)#define rdm(x, i) for(int i=ihead[x]; i; i=e[i].next)inline const int getint() { int r=0, k=1; char c=getchar(); for(; c<‘0‘||c>‘9‘; c=getchar()) if(c==‘-‘) k=-1; for(; c>=‘0‘&&c<=‘9‘; c=getchar()) r=r*10+c-‘0‘; return k*r; }const int N=50005, oo=~0u>>2;int a[N], n, b[N], g[N], pos[N], nxt[N], inext[N], f[N];void init() { for1(i, 1, n) g[i]=oo; for1(i, 1, n) { int k=upper_bound(g+1, g+1+i, b[i])-g; f[i]=k; g[k]=b[i]; nxt[i]=pos[k]; inext[i]=pos[k-1]; pos[k]=i; }}ll ans[N], c[N];void work() { for1(i, 2, n) { int p=inext[i], pos=1; ans[i]=oo; while(p) { if(b[i]>=b[p]) pos=p; p=nxt[p]; } p=pos; ll sum=0, mx=-oo; c[p]=0; for1(j, p+1, i-1) c[j]=c[j-1]+(b[j]<b[i]?1:-1); for3(j, i-1, p) { if(b[j]<=b[i] && f[j]+1==f[i]) { ans[i]=min(ans[i], ans[j]+sum); ans[i]=min(ans[i], ans[j]+sum-(ll)(b[i]-b[j])*(mx-c[j])); } if(mx<c[j]) mx=c[j]; sum+=abs(b[i]-b[j]); } }}int main() { read(n); b[1]=-oo; ++n; for1(i, 2, n) read(a[i]), b[i]=a[i]-i; ++n; b[n]=oo-n; init(); work(); printf("%d\n%lld\n", n-f[n], ans[n]); return 0;}
Description
现在我们有一个长度为n的整数序列A。但是它太不好看了，于是我们希望把它变成一个单调严格上升的序列。但是不希望改变过多的数，也不希望改变的幅度太大。
Input
第一行包含一个数n，接下来n个整数按顺序描述每一项的键值。
Output
第一行一个整数表示最少需要改变多少个数。 第二行一个整数，表示在改变的数最少的情况下，每个数改变的绝对值之和的最小值。
Sample Input
5 2 3 5
Sample Output
4
HINT
【数据范围】
90%的数据n<=6000。
100%的数据n<=35000。
保证所有数列是随机的。
Source
【BZOJ】1049: [HAOI2006]数字序列（lis+特殊的技巧）