fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define ____AnhKietSS____ ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  4. #define NamDinh signed
  5. #define ll long long
  6. #define foru(i,d,c) for(int i=(d);i<=(c);i++)
  7. #define ford(i,d,c) for(int i=(d);i>=(c);i--)
  8. #define fi first
  9. #define se second
  10. #define pb push_back
  11. #define INF 4557430888798830399LL
  12.  
  13. using namespace std;
  14.  
  15. const int N=305;
  16.  
  17. int n;
  18. ll k;
  19. ll h[N],c[N];
  20.  
  21. struct Node
  22. {
  23.     ll h,c;
  24.     int id;
  25. };
  26.  
  27. NamDinh main()
  28. {
  29.     ____AnhKietSS____
  30.  
  31.  
  32.  
  33.     cin>>n>>k;
  34.  
  35.     foru(i,1,n)
  36.     {
  37.         cin>>h[i]>>c[i];
  38.     }
  39.  
  40.     /*
  41.         Ý tưởng:
  42.  
  43.         Với một phương án cuối cùng, các điểm có cùng độ cao tạo thành
  44.         một "tầng".
  45.  
  46.         Các tầng phải có độ cao tăng dần.
  47.  
  48.         Nếu tầng trước có p điểm và tầng hiện tại có s điểm:
  49.  
  50.         - Mỗi điểm ở tầng trước ban đầu có 1 trạm.
  51.         - Ta có p trạm miễn phí.
  52.         - Nếu s > p thì phải xây thêm s-p trạm.
  53.         - Những trạm thêm này luôn nên xây tại điểm có C nhỏ nhất
  54.           trong tất cả các tầng trước.
  55.  
  56.         Sau khi xử lý một tầng, số trạm miễn phí còn lại tương đương
  57.         với max(p,s).
  58.  
  59.         Vì N <= 300, có thể DP theo số điểm của tầng hiện tại,
  60.         số trạm miễn phí lớn nhất và điểm có C nhỏ nhất.
  61.  
  62.         Ta thử từng điểm làm khách sạn.
  63.     */
  64.  
  65.     /*
  66.         Code dưới đây dùng DP theo thứ tự độ cao.
  67.  
  68.         dp[i][j] = chi phí nhỏ nhất khi đã xử lý i điểm,
  69.         tầng hiện tại có j điểm.
  70.  
  71.         Tuy nhiên việc chọn tập điểm của từng tầng phụ thuộc cả H,C,
  72.         nên ta sắp xếp theo H và dùng DP nhóm liên tiếp.
  73.  
  74.         Trong phương án tối ưu, các điểm trong cùng tầng có thể
  75.         sắp theo H tăng dần; nếu đổi chỗ hai tầng thì tầng có H lớn
  76.         hơn không thể đứng trước tầng có H nhỏ hơn mà làm giảm chi phí
  77.         nâng độ cao.
  78.  
  79.         Vì vậy sau khi sort H, ta xét các đoạn liên tiếp làm một tầng.
  80.     */
  81.  
  82.     vector<Node> a(n);
  83.  
  84.     foru(i,1,n)
  85.     {
  86.         a[i-1].h=h[i];
  87.         a[i-1].c=c[i];
  88.         a[i-1].id=i;
  89.     }
  90.  
  91.     sort(a.begin(),a.end(),[](const Node &x,const Node &y)
  92.     {
  93.         if(x.h!=y.h)
  94.             return x.h<y.h;
  95.         return x.c<y.c;
  96.     });
  97.  
  98.     ll ans=INF;
  99.  
  100.     /*
  101.         dp[l][r]:
  102.  
  103.         Chọn [l..r] làm một tầng.
  104.  
  105.         mx = max H trong đoạn.
  106.         Độ cao tầng phải lớn hơn tầng trước ít nhất 1.
  107.  
  108.         Ta dùng DP theo số lượng phần tử của tầng trước.
  109.     */
  110.  
  111.     foru(root,0,n-1)
  112.     {
  113.         vector<Node> b;
  114.         b.pb(a[root]);
  115.  
  116.         foru(i,0,n-1)
  117.         {
  118.             if(i!=root)
  119.                 b.pb(a[i]);
  120.         }
  121.  
  122.         sort(b.begin(),b.end(),[](const Node &x,const Node &y)
  123.         {
  124.             if(x.h!=y.h)
  125.                 return x.h<y.h;
  126.             return x.c<y.c;
  127.         });
  128.  
  129.         /*
  130.             root được xem là tầng đầu tiên.
  131.  
  132.             Vì root là khách sạn nên nó không cần đường trượt đi ra.
  133.         */
  134.  
  135.         int m=n;
  136.  
  137.         vector<vector<ll> > dp(m+1,vector<ll>(m+1,INF));
  138.  
  139.         dp[1][1]=0;
  140.  
  141.         foru(i,1,m-1)
  142.         {
  143.             foru(s,1,m-i+1)
  144.             {
  145.                 if(dp[i][s]>=INF)
  146.                     continue;
  147.  
  148.                 ll lastH=b[i-1].h;
  149.  
  150.                 ll mx=b[i].h;
  151.  
  152.                 foru(j,i,m-1)
  153.                 {
  154.                     mx=max(mx,b[j].h);
  155.  
  156.                     int ns=j-i+1;
  157.  
  158.                     if(i+ns>m)
  159.                         break;
  160.  
  161.                     ll nh=max(mx,lastH+1);
  162.  
  163.                     ll add=0;
  164.  
  165.                     foru(t,i,j)
  166.                     {
  167.                         add+=k*(nh-b[t].h);
  168.                     }
  169.  
  170.                     /*
  171.                         Nếu tầng mới có nhiều điểm hơn tầng trước,
  172.                         cần thêm trạm.
  173.  
  174.                         Ta lấy C nhỏ nhất trong các điểm đã xuất hiện.
  175.                     */
  176.  
  177.                     ll mc=INF;
  178.  
  179.                     foru(t,0,i-1)
  180.                         mc=min(mc,b[t].c);
  181.  
  182.                     if(ns>s)
  183.                         add+=(ll)(ns-s)*mc;
  184.  
  185.                     int ni=j+1;
  186.  
  187.                     dp[ni][ns]=min(dp[ni][ns],dp[i][s]+add);
  188.  
  189.                     lastH=nh;
  190.                 }
  191.             }
  192.         }
  193.  
  194.         foru(s,1,m)
  195.             ans=min(ans,dp[m][s]);
  196.     }
  197.  
  198.     cout<<ans<<"\n";
  199.  
  200.     return 0;
  201. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
5 2
0 6
1 1
0 5
2 1
1 2
stdout
copy 
4
https://ideone.com/vTXHHh
language:
C++ (gcc 8.3)
created:
8 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!