DP_1d1d诗人小G-白红宇

DP_1d1d诗人小G

阅读量：6091 次

发布时间：2019-06-20

本文共 1518 字，大约阅读时间需要 5 分钟。

显然：f[i]=min{f[j]+(s[i]-s[j]+i-j-1-l)^p}

此题可以基于决策单调优化

实际上就是双向队列

不停弹出队头的元素，直到当前位置在队头元素最优的范围内。

然后，每次把当前决策插入队尾，并弹出没它优的答案。

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #include 
              10 #include 
               
                11 using namespace std;12 13 typedef long double ll;14 const int MAXN=1e5+10;15 struct node{ int l,r,p;}q[MAXN];16 ll sum[MAXN],f[MAXN];17 int T,n,l,p;18 char s[35];19 20 ll pow(ll x){21 int y=p;ll ret=1;22 while(y){23 if(y&1)ret=ret*x;24 x*=x,y>>=1;25 }26 return ret;27 }28 29 ll calc(int x,int y){30 return f[x]+pow(abs(sum[y]-sum[x]+(y-x-1)-l));31 }32 33 int find(node x,int i){34 int l=x.l,r=x.r;35 while(l<=r){36 int mid=(l+r)>>1;37 if(calc(i,mid)<=calc(x.p,mid))r=mid-1;38 else l=mid+1;39 }40 return l;41 }42 43 void DP_1d1d(){44 int head=1,tail=0;45 q[++tail]=(node){ 0,n,0};46 for(int i=1;i<=n;i++){47 if(head<=tail && q[head].r
                
                 =calc(i,q[tail].l) )tail--;51 if(head>tail)q[++tail]=(node){i,n,i};52 else{53 int x=find(q[tail],i);54 q[tail].r=x-1;55 q[++tail]=(node){x,n,i};56 }57 }58 }59 }60 61 int main(){62 scanf("%d",&T);63 while(T--){64 scanf("%d%d%d",&n,&l,&p);65 for(int i=1;i<=n;i++)scanf("%s",s),sum[i]=sum[i-1]+strlen(s);66 DP_1d1d();67 if(f[n]>1e18)puts("Too hard to arrange");68 else printf("%lld\n",(long long)f[n]);69 puts("--------------------");70 }71 return 0;72 }