[hdu6580]Milk
考虑定义以下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})$
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 }
转载于//www.cnblogs.com/PYWBKTDA/p/11257693.html
还没有评论,来说两句吧...