题目链接：传送门

Description

给你一个长为n的序列要填满，已知填上第i个数花费的代价为ai，把当前序列循环右移一位花费的代价为x，求最小代价。

Hint

N <= 2000, ai <= 10^9, x <= 10^9

Input

N x a1 a2 ... aN

Output

Find the minimum time that Snuke needs to have slimes in all N colors.

Sample Input

2 10 1 100

Sample Output

12

Solution

这道题想了很久没想出来，看了题解，发现自己完全想错了。。。 我们可以枚举最多循环向后移动i次，那么对于每一个j来说，它一定是从它前面i个数中最小的那一个转移过来，预处理一个区间最小值即可

Summary

这种题的套路还是不是很熟悉

听sxy说这种N^2的题的套路一般都是先O（N）枚举一个东西，然后再O（N）去计算答案。然后一些数据范围更大的题就是O（1）或者log去计算答案。这道题就当做是一个积累，以后做题的时候要往这方面想

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int Maxn = 2000 + 100;
int N;
LL M;
LL A[Maxn], Min[Maxn][Maxn];
int main()
{
#ifdef hk_cnyali
    freopen("B.in", "r", stdin);
    freopen("B.out", "w", stdout);
#endif
    scanf("%d%lld", &N, &M);
    for (int i = 1; i <= N; ++i) scanf("%lld", &A[i]);
    for (int i = 1; i <= N; ++i) Min[i][i] = A[i];
    for (int i = 1; i <= N; ++i)
        for (int j = i + 1; j <= N; ++j)
            Min[i][j] = min(Min[i][j - 1], A[j]);
    LL Ans = 0x3f3f3f3f3f3f3f3f;
    for (int i = 0; i < N; ++i)
    {
        LL Sum = i * M;
        for (int j = 1; j <= N; ++j)
            if (j > i) Sum += Min[j - i][j];
            else Sum += min(Min[1][j], Min[j - i + N][N]);
        Ans = min(Ans, Sum);
    }
    cout<<Ans<<endl;
    return 0;
}