[hdu6580]Milk

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

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

发表评论

表情:
评论列表 (有 0 条评论,304人围观)

还没有评论,来说两句吧...

相关阅读

    相关 【杭电1070】Milk

    ![这里写图片描述][20160721084340435] ![这里写图片描述][20160721084352546] 最重要的思想是在输入的时候去掉多余的输入数据。

    相关 [hdu6580]Milk

    考虑定义以下dp数组: 1.g1\[i\]\[j\]表示第i行从中间出发向左取j瓶牛奶最少要多久 2.g2\[i\]\[j\]表示第i行从中间出发向右取j瓶牛奶最少要多