Advertisement
WayKillerZ

SLIME

May 24th, 2022
631
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.     int dp[2006], a[2006], v[2006];
  42.    
  43.     /* Khoi tao, tim vi tri phan tu nho nhat */
  44.  
  45.     int n, x;
  46.     int m = INF, pos;
  47.     cin >> n >> x;
  48.  
  49.     for(int i = 0; i < n; i++){
  50.         cin >> a[i];
  51.         if(a[i] < m) {
  52.             m = a[i];
  53.             pos = i;
  54.         }
  55.     }
  56.    
  57.  
  58.     /*
  59.     *   Xoay mang A sao cho phan tu nho nhat nam o vi tri dau tien
  60.     *   VD:  4 5 6 1 2 3
  61.     *   --> 1 2 3 4 5 6
  62.     */
  63.     for(int i = pos; i < n; i++) v[i - pos] = a[i];
  64.     for(int i = 0; i < pos; i++) v[n - pos + i] = a[i];
  65.  
  66.  
  67.     /*  Quy hoach dong
  68.     *   dp[i] la gia tri nho nhat de tao ra cac cuc slime tinh den
  69.     *   vi tri thu i cua mang V (mang A sau khi xoay)
  70.     *  
  71.     *   Co 2 truong hop de tao them mot cuc slime o vi tri thu i:
  72.     *   1. Bien doi tat ca cuc slime hien co, tao ra them mot cuc slime
  73.     *   o vi tri dau tien
  74.     *   2. Tao ra them mot cuc slime o vi tri thu i
  75.     *
  76.     *   => Cong thuc: dp[i] = min(dp[i-1] + x + v[0], dp[i-1] + v[i]);
  77.     *   Dap an la dp[n-1] (vi tri cuoi cung cua mang)
  78.     */
  79.  
  80.     dp[0] = v[0];
  81.     for(int i = 1; i < n; i++)
  82.         dp[i] = min(dp[i-1] + v[i], dp[i-1] + x + v[0]);
  83.  
  84.     cout << dp[n-1] << endl;
  85.  
  86.     return 0;
  87. }
Advertisement
RAW Paste Data Copied
Advertisement