CF1175G Yet Another Partiton Problem解题报告

解题报告

CF1175G Yet Another Partiton Problem解题报告：

题意

分析

代码

保留了一部分DEBUG内容，鬼知道我是怎么把二分斜率的地方写错的。

#include<stdio.h>
#include<queue>
#define inf 1000000000
using namespace std;
const int maxn=20005,maxk=maxn*20;
int n,k,now,lst,top,tot;
int a[maxn],b[maxn],f[2][maxn],stk[maxn],lc[maxk],rc[maxk],ans[maxk],rt[maxn];
deque<int>con[maxn];
inline int calc(int id,int X){
    return a[id]*X+b[id];
}
inline int newnode(int x){
    tot++,lc[tot]=lc[x],rc[tot]=rc[x],ans[tot]=ans[x];
    return tot;
}
void update(int l,int r,int now,int pos){
//  printf("now=%d ",now);
    if(l==r){
//      printf("\n!!!!!!!!!!!!!!! %d %d %d %d\n",l,r,now,pos);
        if(calc(ans[now],l)>calc(pos,l))
            ans[now]=pos;
        return ;
    }
    int mid=(l+r)>>1;
    if(calc(ans[now],mid)>calc(pos,mid))
        swap(ans[now],pos);
    if(calc(ans[now],l)>calc(pos,l))
        lc[now]=newnode(lc[now]),update(l,mid,lc[now],pos);
    else rc[now]=newnode(rc[now]),update(mid+1,r,rc[now],pos);
}
int query(int l,int r,int now,int X){
    if(l==r)
        return calc(ans[now],X);
    int mid=(l+r)>>1,res;
    if(X<=mid)
        res=query(l,mid,lc[now],X);
    else res=query(mid+1,r,rc[now],X);
    return min(res,calc(ans[now],X));
}
inline int x(int p){
    return p;
}
inline int y(int p){
    return f[lst][p];
}
inline double slope(int a,int b){
    return x(a)==x(b)? (y(a)>y(b)? inf:-inf):1.0*(y(a)-y(b))/(x(a)-x(b));
}
void merge_convex(int a,int b){
    int flg=0;
    if(con[a].size()>con[b].size()){
        while(!con[b].empty()){
            int p=con[b].back();
            while(con[a].size()>1&&slope(con[a][1],p)>=slope(con[a][1],con[a][0]))
                con[a].pop_front();
            con[a].push_front(p),con[b].pop_back();
        }
    }
    else{
        for(int i=0;i<con[a].size();i++){
            int p=con[a][i];
            while(con[b].size()>1&&slope(p,con[b][con[b].size()-2])<=slope(con[b].back(),con[b][con[b].size()-2]))
                con[b].pop_back();
            con[b].push_back(p);
        }
        con[a].clear(),swap(con[a],con[b]);
    }
}
int find(int p,int X){
    int L=1,R=con[p].size()-1;
//  for(int i=0;i<con[p].size();i++)
//      printf("%d(%d) ",con[p][i],f[lst][con[p][i]]);
//  puts("");
    while(L<=R){
        int mid=(L+R)>>1;
        if(slope(con[p][mid],con[p][mid-1])<1.0*X)
            L=mid+1;
        else R=mid-1;
    }
//  printf("L=%d(%d,%d)\n",L-1,con[p][L-1],f[lst][con[p][L-1]]-(con[p][L-1]-1)*X);
    return f[lst][con[p][L-1]]-(con[p][L-1]-1)*X;
}
int main(){
    scanf("%d%d",&n,&k);
    int tmp=0;
    a[0]=0,b[0]=inf;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        tmp=max(tmp,a[i]),f[0][i+1]=i*tmp;
    }
    now=1,lst=0;
    for(int i=2;i<=k;i++){
        top=tot=0;
        for(int j=i;j<=n;j++){
            con[j].clear(),con[j].push_back(j);
            while(top>0&&a[j]>=a[stk[top]])
                merge_convex(j,stk[top]),top--;
            rt[j]=newnode(rt[stk[top]]),stk[++top]=j;
//          printf("rt[j]=%d\n",rt[j]);
            b[j]=find(j,a[j]),update(1,n,rt[j],j),f[now][j+1]=query(1,n,rt[j],j);
//          printf("i=%d j=%d f[now][j+1]=%d b=%d a=%d\n",i,j,f[now][j+1],b[j],a[j]);
        }
        lst=now,now^=1;
    }
    printf("%d\n",f[lst][n+1]);
    return 0;
}