题目传送门：http://codeforces.com/contest/713/problem/C
我™之前做过这原题！然而考试的时候没想到怎么做QAQ
I well vegatable are!
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 3000+9;
const LL INF = 1e15;
int arr[N],hash[N],n,tot;
LL f[N][N],MN[N];
inline int read(){
char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}
#define update(x,y) (x=((x)==-1||(y)<(x)?(y):(x)))
#define abs(x) ((x)>0?(x):-(x))
int main(){
n = read();
for (int i=1;i<=n;i++) hash[i] = arr[i] = read() - i;
sort(hash+1,hash+1+n); tot = unique(hash+1,hash+1+n) - hash - 1;
for (int i=1;i<=n;i++) memset(f[i],-1,sizeof(f[i])), MN[i] = -1;
for (int i=1;i<=n;i++) {
LL best = INF;
for (int j=1;j<=tot;j++) {
if (~f[i-1][j]) best = min(best, f[i-1][j]);
update(f[i][j],best+abs(arr[i]-hash[j]));
}
}
LL vout = INF;
for (int i=1;i<=tot;i++) if (~f[n][i])
vout = min(vout, f[n][i]);
cout<<vout;
return 0;
}
至于为什么减去下标答案不会变？
我们可以考虑差分序列啦！
—– UPD 2016.9.14 —–
这题看策爷的代码，可以用左偏树搞到O(nlogn)
原来这个题目可以贪心！
考虑最后的样子，一定长这样：
加入一个堆，其中位数不满足整体不减的话，即与左边的堆合并
为什么这么贪心的是对的呢？因为不管你砍哪一步分开，那一部分的差距都会更大，即不可能成为最优解
Remarkable things here. I’m very glad to see your post.
Thanks so much and I am having a look ahead to contact you.
Will you please drop me a mail?
I think this is one of the most important info for me.
And i’m glad reading your article. But want to remark on some general
things, The website style is great, the articles is really great
: D. Good job, cheers
It is in reality a nice and useful piece of information. I’m
happy that you just shared this helpful info with us. Please keep us informed like this.
Thank you for sharing.
Your style is unique in comparison to other people I’ve read stuff from.
Thank you for posting when you have the opportunity, Guess I’ll just book mark this
page.
Hi there to every one, because I am genuinely
eager of reading this web site’s post to
be updated regularly. It carries pleasant information.
I loved as much as you will receive carried out right here.
The sketch is tasteful, your authored material stylish.
nonetheless, you command get got an nervousness over that you wish be delivering the following.
unwell unquestionably come further formerly again since exactly the same nearly
very often inside case you shield this hike.
Hi there, I enjoy reading all of your article.
I wanted to write a little comment to support you.
Hi to every body, it’s my first go to see of this web site; this weblog
carries amazing and actually excellent data in favor of readers.
Thanks very interesting blog!
I seriously love your website.. Pleasant colors & theme. Did you make this
amazing site yourself? Please reply back as I’m attempting to create
my own site and want to know where you got this from or what the theme
is named. Many thanks!
Great article, exactly what I needed.
Hello, I think your site might be having browser compatibility issues.
When I look at your website in Ie, it looks fine but when opening in Internet Explorer, it has some overlapping.
I just wanted to give you a quick heads up! Other then that, amazing
blog!
Hi, I do believe this is an excellent site. I stumbledupon it 😉 I’m going to return yet again since i have bookmarked it.
Money and freedom is the best way to change, may you be rich and continue to guide other people.
I have read so many articles or reviews on the topic
of the blogger lovers however this post is in fact a good post, keep it up.
My partner and I stumbled over here by a different website and thought I
might check things out. I like what I see so i am just following
you. Look forward to looking into your web page repeatedly.
You have made some good points there. I looked on the
net for more info about the issue and found most people will go along with your views on this web site.
Thanks for sharing such a nice thinking, paragraph is good, thats why i have read it completely
I visited various web pages but the audio quality for audio songs present at this web site is
genuinely marvelous.