[hdu6580]Milk

水深无声 2021-11-17 15:32 162阅读 0赞

考虑定义以下dp数组：  
1.g1\[i\]\[j\]表示第i行从中间出发向左取j瓶牛奶最少要多久  
2.g2\[i\]\[j\]表示第i行从中间出发向右取j瓶牛奶最少要多久  
3.g3\[i\]\[j\]表示在g1\[i\]\[j\]的基础上回到中间最少要多久  
4.g4\[i\]\[j\]表示在g2\[i\]\[j\]的基础上回到中间最少要多久  
5.f1\[i\]\[j\]表示第i行从中间出发取到j瓶牛奶最少要多久  
6.f2\[i\]\[j\]表示在f1\[i\]\[j\]的基础上回到中间最少要多久  
7.f3\[i\]\[j\]表示从(1,1)出发前i行取到j个物品最少要多久  
8.f4\[i\]\[j\]表示在f3\[i\]\[j\]的基础上回到中间最少要多久(不算向下操作)  
可以用dp算出以上八个数组（可以一起算就不用开vector），然后就可以用f3算出ans，时间复杂度$o(k^\{2\})$

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<bits/stdc++.h>
     2 using namespace std;
     3 #define N 10005
     4 #define inf 1000000LL*0x3f3f3f3f
     5 #define ll long long
     6 struct ji{
     7     int id,x,y,z;
     8     bool operator < (const ji &k)const{
     9         return (x<k.x)||(x==k.x)&&(y<k.y);
    10     }
    11 }a[N];
    12 set<int>s;
    13 int T,n,m;
    14 ll sum,g1[N],g2[N],g3[N],g4[N],f1[N],f2[N],f3[N],f4[N];
    15 void calc(ll *x,ll *y,int l,int r,int t,int p){ 
    16     for(int j=1,k;j!=(r-l)*p+1;j++){
    17         s.clear();
    18         sum=0;
    19         for(k=l;abs(k-l)<j;k+=p){
    20             s.insert(a[k].z);
    21             sum+=a[k].z;
    22         }
    23         x[j]=min(x[j],sum+p*(a[k-p].y-t));
    24         y[j]=min(y[j],sum+p*(a[k-p].y-t)+abs(a[k-p].y-n));
    25         for(;k!=r;k+=p){
    26             int ma=*(--s.end());
    27             if (ma>a[k].z){
    28                 sum-=ma-a[k].z;
    29                 s.erase(--s.end());
    30                 s.insert(a[k].z);
    31             }
    32             x[j]=min(x[j],sum+p*(a[k].y-t));
    33             y[j]=min(y[j],sum+p*(a[k].y-t)+abs(a[k].y-n));
    34         }
    35     }
    36 }
    37 int main(){
    38     scanf("%d",&T);
    39     while (T--){
    40         scanf("%*d%d%d",&n,&m);
    41         n=(n+1)/2;
    42         for(int i=1;i<=m;i++)scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
    43         sort(a+1,a+m+1);
    44         for(int i=1;i<=m;i++)f3[i]=f4[i]=inf;
    45         f3[0]=f4[0]=n-1;
    46         for(int i=1,j;i<=m;){
    47             for(j=i;(j<m)&&(a[j].x==a[j+1].x);j++);
    48             int l=i,r=j,mid;
    49             for(mid=l;(mid<=r)&&(a[mid].y<n);mid++);
    50             for(j=1;j<=r-l+1;j++)g1[j]=g2[j]=g3[j]=g4[j]=inf;
    51             calc(g1,g3,mid-1,l-1,n,-1);
    52             calc(g2,g4,mid,r+1,n,1);
    53             for(j=1;j<=r-l+1;j++)f1[j]=min(g1[j],g2[j]);
    54             for(j=1;j<=r-l+1;j++)f2[j]=min(g3[j],g4[j]);
    55             for(i=1;i<=mid-l;i++)
    56                 for(j=1;j<=r-mid+1;j++){
    57                     f1[i+j]=min(f1[i+j],min(g1[i]+g4[j],g3[i]+g2[j]));
    58                     f2[i+j]=min(f2[i+j],g3[i]+g4[j]);
    59                 }
    60             if (a[l].x==1){
    61                 calc(f3,f4,1,r-l+2,1,1);
    62                 i=r+1;
    63                 continue;
    64             }
    65             for(i=l-1;i>=0;i--)
    66                 for(j=1;j<=r-l+1;j++){
    67                     f3[i+j]=min(f3[i+j],f4[i]+a[l].x-1+f1[j]);
    68                     f4[i+j]=min(f4[i+j],f4[i]+f2[j]);
    69                 }
    70             i=r+1;
    71         }
    72         for(int i=1;i<m;i++)printf("%lld ",f3[i]);
    73         printf("%lld\n",f3[m]);
    74     }
    75 }

转载于:https://www.cnblogs.com/PYWBKTDA/p/11257693.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211116/15fbb2cdaade442d8406e0627ceae81f.png