Slime

#pragma GCC optimize("Ofast")

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <ctime>

#include <vector>
#include <set>
#include <bitset>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <string>

#define int long long
#define II pair<int, int>
#define III pair<int, pair<int, int>>
#define DI pair<double, int>
#define fs first
#define sc second
#define mp(a, b) make_pair(a, b)
#define LINF 9223372036854775807
#define INF 2147483647

using namespace std;

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    freopen("SLIME.INP", "r", stdin);
    freopen("SLIME.OUT", "w", stdout);

    /* Khởi tạo, tìm vị trí phần tử nhỏ nhất */
    int a[2006], v[2006];

    int n, x;
    int m = INF, pos;
    cin >> n >> x;

    for(int i = 0; i < n; i++) {
        cin >> a[i];
        if(a[i] < m) m = a[i], pos = i;
    }

    /*
    *   Vì mọi vị trí có vai trò của mảng A có vai trò như nhau:
    *   Xoay mảng A sao cho phần tử nhỏ nhất nằm ở vị trí đầu tiên
    *   Mảng A trở thành mảng V
    *   VD:  4 5 6 1 2 3
    *   --> 1 2 3 4 5 6
    */
    for(int i = pos; i < n; i++) v[i - pos] = a[i];
    for(int i = 0; i < pos; i++) v[n - pos + i] = a[i];

    /*  Quy hoạch động
    *
    *   Với mỗi vòng lặp, k là số lần biến đổi tất cả cục slime:
    *   Do đó:
    *   Kinh phí ít nhất (chưa tính các lần biến đổi) để tạo ra
    *   slime thứ i là giá trị nhỏ nhất trong khoảng [i-k, i]
    *
    *   Cộng tất cả giá trị đó với x * k, ta được cách tốn kém ít
    *   nhất để tạo ra n cục slime với đúng k lần biến đổi
    */

    int tmp, sum, ans = INF;
    for(int k = 0; k < n; k++) {
        /*
        *   Cách tốn ít kinh phí nhất để tạo ra cục slime đầu tiên
        *   luôn là v[0] vì v[0] nhỏ nhất trong tập V
        */
        sum = v[0];

        for(int i = 1; i < n; i++) {
            tmp = v[i];
            for(int j = max(i-k, 0ll); j <= i; j++)
                tmp = min(tmp, v[j]);

            sum += tmp;
        }

        ans = min(ans, sum + x*k);
    }

    cout << ans << endl;
    return 0;
}