http://www.lydsy.com/JudgeOnline/problem.php?id=1049

The question ： Give a length of n Integer sequence of . Turn it into a monotonic strictly ascending sequence . But I don't want to change too many numbers , I don't want to change too much .1. Ask at least how many changes need to be made . 2. stay 1 The minimum value of the sum of the absolute values of each number change under the condition of .（n<=35000, Random data ）

#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;

}

It's another magic question .orz

First of all, the first question is easy to see

f[i]=min{f[j]+1, a[i]-a[j]>=i-j}

set up b[i]=a[i]-i

have to

f[i]=min{f[j]+1, b[i]>=b[j]}

Then is lis Of log Algorithm ....

The second question , Good God ！！！

First find out , If there is b[i]>=b[j] And f[i]==f[j]+1 when , Section [j, i] All the points in must be greater than b[i] Or less than b[j], Obviously ..

And we're going to [j, i] If a point becomes a legal sequence, there must be a point t, bring [j, t] become b[j],[t+1, i] become b[i].（ In the original sequence it becomes a[j], a[j+1]=a[j]+1, a[j+2]=a[j]+2... such ）

How to prove ？ Can't QAQ

Try to prove ： Consider the best t, hypothesis b[t] Don't become b[j], But to become b'[t]>b[j], And b'[t]<b[i]. Well, because the original b[t]<b[j] perhaps b[t]>b[i], Obviously the cost is b'[t]-b[t]>b[j]-b[t]（ When b[t]<b[j] when ）b[t]-b'[t]>b[t]-b[i]（ When b[t]>b[i] when ）, obtain b[j]<b'[t]<b[i] No, b'[t]=b[j] or =b[i] optimal , Immediate proof .

So this is n^3 Of ,,,,,,,,,,,,,,

Try to make it first n^2. Consider that the current transition point is i

Let's first find out the distance from i The farthest j,b[i]>=b[j] And f[i]==f[j]+1, So all the transition points are contained in the interval [j, i] in .

Consider from i Enumerate left to j, The current in k, At this point, let's assume that all of the [k+1, i-1] All of the points of this change to b[i], So when k It's the transfer point , We need to get the minimum .

Because now [k+1, i-1] It's all turned into b[i], So let's say we're going to change the point into b[j], obviously ： If the original b[x]>b[i], Then the cost still needs +(b[i]-b[j]), If the original b[x]<b[i], Then the cost needs to be -(b[i]-b[j]). hypothesis [k, i] The best of all t,[k+1, t] Yes y Ratio b[i] Big point ,z Ratio b[i] A little bit smaller , So the cost of change is ：

sum-(b[i]-b[k])*z+(b[i]-b[k])*y=sum-(b[i]-b[k])*(z-y), And the interval [j, i] All the transfer points in the project k Obviously b[k] Monotonous , therefore b[i]-b[k] In the monotonous , So the goal becomes maximization (z-y).

So consider the prefix and find the biggest difference ......................................

So the problem becomes n^2...

Then the title says ... Random data ............ Water pass .

（ One more thing to note is , How to find it quickly j spot , So we're in lis To all transfer points , Then find it quickly , Otherwise it would be more complicated ）

## 【BZOJ】1049: [HAOI2006] Number sequence （lis+ Special skills ） More articles about

- bzoj 1049 [HAOI2006] Number sequence
[bzoj1049][HAOI2006] Number sequence Description Now we have a length of n Integer sequence of A. But it's too ugly , So we want to turn it into a monotonic strictly ascending sequence . But I don't want to change too many numbers , either ...

- bzoj 1049: [HAOI2006] Number sequence 【dp+ Two points + fiddle 】
The first question is obviously to use b[i]=a[i]-i To make the longest non descending subsequence And then the second question , For a couple of f[i]=f[j]+1 Of (i,j), The middle number must be changed , And it's equal to b[i] perhaps b[j], I don't know , And then because it's random data , the ...

- 【BZOJ 1049】 1049: [HAOI2006] Number sequence （LIS+ Dynamic programming ）
1049: [HAOI2006] Number sequence Description Now we have a length of n Integer sequence of A. But it's too ugly , So we want to turn it into a monotonic strictly ascending sequence . But I don't want to change too many numbers , I don't want to change ...

- 1049: [HAOI2006] Number sequence - BZOJ
Description Now we have a length of n Integer sequence of A. But it's too ugly , So we want to turn it into a monotonic strictly ascending sequence . But I don't want to change too many numbers , I don't want to change too much .Input The first line contains a number n ...

- Luogu P2501 [HAOI2006] Number sequence Problem solving report
P2501 [HAOI2006] Number sequence Title Description Now we have a length of n Integer sequence of A. But it's too ugly , So we want to turn it into a monotonic strictly ascending sequence . But I don't want to change too many numbers , I don't want to change too much . ...

- 【BZOJ1049】 [HAOI2006] Number sequence
BZOJ1049 [HAOI2006] Number sequence dp Good question ? First question First, I can do ! Make \(b_i=a_i-i\), Find a longest undescending subsequence . \(n-ans\) Is the final answer . Second questions So hard! . Can't . Dig a hole ...

- [luogu2501 HAOI2006] Number sequence ( Recurrence LIS)
Title Description Now we have a length of n Integer sequence of A. But it's too ugly , So we want to turn it into a monotonic strictly ascending sequence . But I don't want to change too many numbers , I don't want to change too much . I / O format Input format : The first line contains a number ...

- 【BZOJ1049】【Luogu P2501】 [HAOI2006] Number sequence DP, Conclusion ,LIS
Have much (\(bu\)) quality (\(hui\)) The amount (\(xie\)) A topic of . First question : A random sequence can be changed into a monotone ascending sequence by changing at least a few numbers . \(Solution:\) It seems to be a conclusion ? If two numbers \(A_i\) ...

- Luogu P2501 bzoj1049 [HAOI2006] Number sequence
Topic link bzoj Luogu Answer key First question : If \(i < j\) If \(j\) Can from \(i\) Turn around Obviously there has to be enough space in the middle for example :\(50\) \(53\) \(53\) \(52\) Just ...

## Random recommendation

- [Hadoop periphery ] Hadoop Data collection 【 turn 】
Original website : http://www.iteblog.com/archives/851 The most direct learning reference website is of course the official website : http://hadoop.apache.org/ Hadoop http:// ...

- jQuery Study - Binding events of events （ 3、 ... and ）
In the last article <jQuery Study - Binding events of events ( Two )> We get it jQuery Of dispatch Method , Let's learn today handlers Method : handlers: function( event ...

- php Check whether the current browser is wechat browser
<?php /** php Check whether the current browser is wechat browser */ function is_weixin_browser(){ if(strpos($_SERVER['HTTP_USER_AGENT ...

- About linux It's time python Script
Pit encountered : Python File operations in scripts , It's best to use the absolute path , On the head of the file is written #!/usr/local/bin/python3.6 ----------------------------------- ...

- Springboot One of the monitors ：SpringBoot One of the four artifact Actuator
Introduce Spring Boot There are four artifacts , Namely auto-configuration.starters.cli.actuator, This article mainly talks about actuator.actuator yes spring boot Provide ...

- 150. Evaluate Reverse Polish Notation Reverse Polish notation
［ Copy questions ］: Evaluate the value of an arithmetic expression in Reverse Polish Notation. Valid operators are ...

- Service Broker summary
ServiceBroker( abbreviation SSB) It is based on a powerful asynchronous programming model provided by database engine , adopt ServiceBroker, Developers don't have to write complex communication and messaging programs , In this way, efficient and reliable asynchronous communication can be achieved between database instances . ...

- php Ranking learning is - Bubble sort
principle : For a set of data , Compare the size of adjacent data , Put the value of small data in the front , The data with large value is put at the back . ( The following are all in ascending order , From small to large ) Illustrate with examples : $arr = array(6, 3, 8, 2, 9, 1); $a ...

- Vue Right-click menu
rightShow(item) { this.isPersoncontextMenus = true; let menu = document.getElementById("msgRigh ...

- leetcode Roman numeral to integer
Roman numerals contain the following seven characters :I,V,X,L,C,D and M. character The number I 1 V 5 X 10 L 50 C 100 D 500 M 1000 for example , Rome digital 2 Write to do II , Two parallel 1.1 ...