WayKillerZ

Slime

May 26th, 2022 (edited)
336
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #pragma GCC optimize("Ofast")
  2.  
  3. #include <iostream>
  4. #include <stdio.h>
  5. #include <algorithm>
  6. #include <iomanip>
  7. #include <cmath>
  8. #include <cstring>
  9. #include <climits>
  10. #include <cstdlib>
  11. #include <ctime>
  12.  
  13. #include <vector>
  14. #include <set>
  15. #include <bitset>
  16. #include <map>
  17. #include <queue>
  18. #include <deque>
  19. #include <stack>
  20. #include <string>
  21.  
  22. #define int long long
  23. #define II pair<int, int>
  24. #define III pair<int, pair<int, int>>
  25. #define DI pair<double, int>
  26. #define fs first
  27. #define sc second
  28. #define mp(a, b) make_pair(a, b)
  29. #define LINF 9223372036854775807
  30. #define INF 2147483647
  31.  
  32. using namespace std;
  33.  
  34. int32_t main() {
  35.     ios_base::sync_with_stdio(false);
  36.     cin.tie(NULL);
  37.    
  38.     freopen("SLIME.INP", "r", stdin);
  39.     freopen("SLIME.OUT", "w", stdout);
  40.    
  41.     /* Khởi tạo, tìm vị trí phần tử nhỏ nhất */
  42.     int a[2006], v[2006];
  43.  
  44.     int n, x;
  45.     int m = INF, pos;
  46.     cin >> n >> x;
  47.  
  48.     for(int i = 0; i < n; i++) {
  49.         cin >> a[i];
  50.         if(a[i] < m) m = a[i], pos = i;
  51.     }
  52.  
  53.     /*
  54.     *   Vì mọi vị trí có vai trò của mảng A có vai trò như nhau:
  55.     *   Xoay mảng A sao cho phần tử nhỏ nhất nằm ở vị trí đầu tiên
  56.     *   Mảng A trở thành mảng V
  57.     *   VD:  4 5 6 1 2 3
  58.     *   --> 1 2 3 4 5 6
  59.     */
  60.     for(int i = pos; i < n; i++) v[i - pos] = a[i];
  61.     for(int i = 0; i < pos; i++) v[n - pos + i] = a[i];
  62.  
  63.     /*  Quy hoạch động
  64.     *  
  65.     *   Với mỗi vòng lặp, k là số lần biến đổi tất cả cục slime:
  66.     *   Do đó:
  67.     *   Kinh phí ít nhất (chưa tính các lần biến đổi) để tạo ra
  68.     *   slime thứ i là giá trị nhỏ nhất trong khoảng [i-k, i]
  69.     *
  70.     *   Cộng tất cả giá trị đó với x * k, ta được cách tốn kém ít
  71.     *   nhất để tạo ra n cục slime với đúng k lần biến đổi
  72.     */
  73.  
  74.     int tmp, sum, ans = INF;
  75.     for(int k = 0; k < n; k++) {
  76.         /*  
  77.         *   Cách tốn ít kinh phí nhất để tạo ra cục slime đầu tiên
  78.         *   luôn là v[0] vì v[0] nhỏ nhất trong tập V
  79.         */
  80.         sum = v[0];
  81.        
  82.         for(int i = 1; i < n; i++) {
  83.             tmp = v[i];
  84.             for(int j = max(i-k, 0ll); j <= i; j++)
  85.                 tmp = min(tmp, v[j]);
  86.  
  87.             sum += tmp;
  88.         }
  89.  
  90.         ans = min(ans, sum + x*k);
  91.     }
  92.    
  93.     cout << ans << endl;
  94.     return 0;
  95. }
RAW Paste Data Copied