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

  1. 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 ...

  2. 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 ...

  3. 【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 ...

  4. 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 ...

  5. 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 . ...

  6. 【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 ...

  7. [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 ...

  8. 【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\) ...

  9. 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

  1. [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:// ...

  2. 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 ...

  3. 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 ...

  4. 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 ----------------------------------- ...

  5. 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 ...

  6. 150. Evaluate Reverse Polish Notation Reverse Polish notation

    [ Copy questions ]: Evaluate the value of an arithmetic expression in Reverse Polish Notation. Valid operators are ...

  7. 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 . ...

  8. 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 ...

  9. Vue Right-click menu

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

  10. 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 ...