【BZOJ 1563】 （四边形优化、决策单调性）

【分析】

　　BZOJ1010玩具装箱的加强版。这里是^p不是平方。

　　这个是经典的1D/1D形式？【所谓1D/1D动态规划，指的是状态数为O(n)，每一个状态决策量为O(n)的动态规划方程。】

　　可以看：1D/1D动态规划优化初步，这题是经典的模型一

　　

　　证明自己化式子啊。。

　　然后就是决策单调的意思，最优取值点不断右移。

　　

　　

　　这个为什么我觉得写栈有点尴尬【要二分两次？】，双向链表就很好啊~~

　　st[i]表示i这个点的决策区间的起始位置，结束位置为nt的起始的前一位或n。

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 using namespace std;

 #define LL long long

 #define LD long double

 #define Maxn 100010

 const long double INF=1e18;

 char s[];

 LD a[Maxn],f[Maxn],len[Maxn],sm[Maxn],L;

 int lt[Maxn],nt[Maxn],st[Maxn],P;

 LD qpow(LD x,int b)

 {

     if(x<) x=-x;

     LD ans=1.0;

     while(b)

     {

         if(b&) ans*=x;

         x*=x;

         b>>=;

     }

     return ans;

 }

 LD cal(int i,int j)

 {

     return f[j]+qpow(sm[i]-sm[j]+(LD)i-(LD)j-1.0-L,P);

 }

 bool check(int mid,int x,int y)

 {

     return cal(mid,x)>=cal(mid,y);

 }

 int n;

 int ffind(int l,int r,int x,int y)

 {

     int ans=n+;

     while(l<=r)

     {

         int mid=(l+r)>>;

         if(check(mid,x,y)) ans=mid,r=mid-;

         else l=mid+;

     }

     return ans;

 }

 int main()

 {

     int T;

     scanf("%d",&T);

     while(T--)

     {

         cin>>n>>L>>P;sm[]=;

         for(int i=;i<=n;i++)

         {

             scanf("%s",s);len[i]=(LD)strlen(s);

             sm[i]=sm[i-]+len[i];

         }

         for(int i=;i<=n;i++) f[i]=INF+,st[i]=n+,lt[i]=i-,nt[i]=i+;

         f[]=;st[]=;

         int now=;

         for(int i=;i<=n;i++)

         {

             while(st[nt[now]]<=i) now=nt[now];

             f[i]=cal(i,now);

             while(st[lt[i]]>i)

             {

                 if(check(st[lt[i]],lt[i],i))

                 {

                     lt[i]=lt[lt[i]];

                     nt[lt[i]]=i;

                 }

                 else break;

             }

             st[i]=ffind(st[lt[i]],n,lt[i],i);

             if(st[i]>n) nt[lt[i]]=nt[i],lt[nt[i]]=lt[i];

         }

         if(f[n]>INF) printf("Too hard to arrange\n");

         else cout<<(LL)f[n]<<endl;

         printf("--------------------\n");

     }

     return ;

 }

2017-04-26 10:06:39