| 记录编号 |
143706 |
评测结果 |
AAAAAAAAAAAAAAAAAAAA |
| 题目名称 |
[国家集训队2011]K凹凸序列 |
最终得分 |
100 |
| 用户昵称 |
 cstdio |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
0.501 s |
| 提交时间 |
2014-12-17 07:28:25 |
内存使用 |
8.90 MiB |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
const int SIZEN1=20010,SIZEN2=1010,INF=0x7fffffff/2;
class Node{//大根堆的左偏树
public:
int lc,rc;
int h,val;
};
class Left_Tree{
public:
Node Tree[SIZEN1];
#define lc(x) Tree[x].lc
#define rc(x) Tree[x].rc
#define h(x) Tree[x].h
#define val(x) Tree[x].val
void init(int x,int t){
lc(x)=rc(x)=h(x)=0;
val(x)=t;
}
int Get_Val(int u){
return val(u);
}
int Erase(int u){
return Merge(lc(u),rc(u));
}
int Merge(int u,int v){
if(!u||!v) return u+v;
if(val(u)<val(v)) swap(u,v);
rc(u)=Merge(rc(u),v);
if(h(lc(u))<h(rc(u))) swap(lc(u),rc(u));
h(u)=h(rc(u))+1;
return u;
}
//麻麻再也不用担心define在外面出歧义了......
#undef lc
#undef rc
#undef h
#undef val
};
Left_Tree LT;
class Sub_Seq{//连续段
public:
int l,r;
int root;
int innum,insum;//被选中的数量,总和
int sum;//总和
int midval(void){
return LT.Get_Val(root);
}
int cost(void){
int v=midval();
return (innum*v-insum)+(sum-insum-(r-l+1-innum)*v);
}
void Merge(Sub_Seq b){//b必须紧随其后
r=b.r;
root=LT.Merge(root,b.root);
innum+=b.innum,insum+=b.insum;
sum+=b.sum;
while(innum*2>r-l+2){
innum--;insum-=LT.Get_Val(root);
root=LT.Erase(root);
}
}
};
vector<Sub_Seq> subs;
void Insert(int x,int t,int &cost){
Sub_Seq now;
now.l=now.r=now.root=x;
LT.init(x,t);
now.innum=1;now.insum=t;now.sum=t;
cost+=now.cost();
subs.push_back(now);
while(subs.size()>=2&&subs.back().midval()<subs[subs.size()-2].midval()){
cost-=subs.back().cost()+subs[subs.size()-2].cost();
subs[subs.size()-2].Merge(subs.back());
subs.pop_back();
cost+=subs.back().cost();
}
}
int N,K;
int A[SIZEN1];
void Solve_1(void){//K=1,全部弄成一样
sort(A+1,A+1+N);
int ans=0,mid=A[N/2];
for(int i=1;i<=N;i++) ans+=abs(A[i]-mid);
printf("%d\n",ans);
}
void Solve_2(void){//K=2,弄成递增或递减
int ans=INF,cost;
cost=0;subs.clear();
for(int i=1;i<=N;i++) Insert(i,A[i],cost);
ans=min(ans,cost);
cost=0;subs.clear();
for(int i=1;i<=N;i++) Insert(i,-A[i],cost);
ans=min(ans,cost);
printf("%d\n",ans);
}
void Solve_3(void){//K=3,是A型或V型
static int pinc[SIZEN1]={0},pdec[SIZEN1]={0};
static int sinc[SIZEN1]={0},sdec[SIZEN1]={0};
int ans=INF,cost;
cost=0;subs.clear();
for(int i=1;i<=N;i++) Insert(i,A[i],cost),pinc[i]=cost;
cost=0;subs.clear();
for(int i=1;i<=N;i++) Insert(i,-A[i],cost),pdec[i]=cost;
cost=0;subs.clear();
for(int i=N;i>=1;i--) Insert(N+1-i,A[i],cost),sdec[i]=cost;
cost=0;subs.clear();
for(int i=N;i>=1;i--) Insert(N+1-i,-A[i],cost),sinc[i]=cost;
for(int i=1;i<=N+1;i++){//"转折点",注意这里考虑了全增/减的情况
ans=min(ans,pinc[i-1]+sdec[i]);
ans=min(ans,pdec[i-1]+sinc[i]);
}
printf("%d\n",ans);
}
void Prepare_Sub_Cost(int A[],int s[SIZEN2][SIZEN2]){
for(int i=1;i<=N;i++){
int cost=0;subs.clear();
for(int j=i;j<=N;j++){
Insert(j,A[j],cost);
s[i][j]=cost;
}
}
}
void Solve_Other(void){//其余情况,DP
K--;//K凹凸,即至多K-1个单调段
static int inc[SIZEN2][SIZEN2]={0},dec[SIZEN2][SIZEN2]={0};
Prepare_Sub_Cost(A,inc);
for(int i=1;i<=N;i++) A[i]*=-1;
Prepare_Sub_Cost(A,dec);
static int f[SIZEN2][15]={0},g[SIZEN2][15]={0};
for(int i=0;i<SIZEN2;i++) for(int j=0;j<15;j++) f[i][j]=INF;
for(int i=0;i<SIZEN2;i++) for(int j=0;j<15;j++) g[i][j]=INF;
f[0][0]=g[0][0]=0;
for(int i=1;i<=N;i++){
for(int j=1;j<=K;j++){
for(int i1=0;i1<i;i1++){//枚举上一个单调段的终点
f[i][j]=min(f[i][j],g[i1][j-1]+inc[i1+1][i]);
g[i][j]=min(g[i][j],f[i1][j-1]+dec[i1+1][i]);
}
}
}
int ans=INF;
for(int i=1;i<=K;i++) ans=min(ans,f[N][i]);
for(int i=1;i<=K;i++) ans=min(ans,g[N][i]);
printf("%d\n",ans);
}
void Read(void){
scanf("%d%d",&N,&K);
for(int i=1;i<=N;i++) scanf("%d",&A[i]);
}
int main(){
freopen("zigzag.in","r",stdin);
freopen("zigzag.out","w",stdout);
Read();
if(K==1) Solve_1();
else if(K==2) Solve_2();
else if(K==3) Solve_3();
else Solve_Other();
return 0;
}