poj3016

题解

求n编的poj3666

然后dp

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=100005,M=1005;
int num[N],rt[N],size[N],T,tot,k,val[N],l[N],r[N],a[N],b[N],dist[N];
int c[N][2],dp[N][15],n,m,cost[M][M],cost1[M][M],cost2[M][M];
int merge(int x,int y)
{
    if (!x||!y)return x+y;
    if (val[x]<val[y])swap(x,y);
    c[x][1]=merge(c[x][1],y);
    size[x]=size[c[x][0]]+size[c[x][1]]+1;
    if (dist[c[x][0]]<dist[c[x][1]])swap(c[x][0],c[x][1]);
    dist[x]=dist[c[x][1]]+1;
    return x;
}
void pop(int &x){x=merge(c[x][0],c[x][1]);}
int newnode(int x)
{
    size[++tot]=1;
    val[tot]=x;
    c[tot][0]=c[tot][1]=dist[tot]=0;
    return tot;
}
void makecost1()
{
    int res=0,cnt=0;
    for (int j=1;j<=n;j++)
     {
         tot=res=cnt=0;
        for (int i=j;i<=n;i++)
          {
             rt[++cnt]=newnode(b[i]);
             l[cnt]=r[cnt]=i;num[cnt]=1;
             while (cnt>1&&val[rt[cnt-1]]>val[rt[cnt]])
               {
                 cnt--;
                 if (num[cnt+1]&1)res+=(val[rt[cnt]]-val[rt[cnt+1]]);
                 num[cnt]+=num[cnt+1];
                rt[cnt]=merge(rt[cnt],rt[cnt+1]);
                r[cnt]=r[cnt+1];
                while (size[rt[cnt]]*2>r[cnt]-l[cnt]+2)pop(rt[cnt]);
              } 
             cost1[j][i]=res;  
          }
     }
}
void makecost2()
{
    int res=0,cnt=0;
    for (int j=1;j<=n;j++)
     {
         tot=res=cnt=0;
        for (int i=j;i<=n;i++)
          {
             rt[++cnt]=newnode(b[i]);
             l[cnt]=r[cnt]=i;num[cnt]=1;
             while (cnt>1&&val[rt[cnt-1]]>val[rt[cnt]])
               {
                 cnt--;
                 if (num[cnt+1]&1)res+=(val[rt[cnt]]-val[rt[cnt+1]]);
                 num[cnt]+=num[cnt+1];
                rt[cnt]=merge(rt[cnt],rt[cnt+1]);
                r[cnt]=r[cnt+1];
                while (size[rt[cnt]]*2>r[cnt]-l[cnt]+2)pop(rt[cnt]);
              } 
             cost2[j][i]=res;  
          }
     }
}
void doit()
{
    for (int i=1;i<=n;i++)scanf("%d",&a[i]),b[i]=a[i]-i;
    makecost1();
    for (int i=1;i<=n;i++)b[i]=-a[i]-i;
    makecost2();
    memset(dp,0x3f,sizeof dp);
    dp[0][0]=0;
    for (int i=1;i<=n;i++)
     for (int j=i;j<=n;j++)cost[i][j]=min(cost1[i][j],cost2[i][j]);
    for (int i=1;i<=n;i++)
     for (int j=1;j<=k&&j<=i;j++)
      for (int p=j-1;p<i;p++)
       dp[i][j]=min(dp[i][j],dp[p][j-1]+cost[p+1][i]);
    printf("%d
",dp[n][k]);   
}
int main()
{
    while (~scanf("%d%d",&n,&k),n|k)doit();
}