$ {\scr \color {Orchid}{\text{生於塵埃，溺於人海，死於理想高臺。}}} $

題目鏈接:Colorful Slimes

$ {\scr \color {Cyan}{\text{Solution}}} $

分析

思路：挺神奇的$dp$

一個比較顯然的結論：最小值的方案中第$2$種操作最多用$n-1$次

證明大概就是一個數用$n-1$次一定會變成另一個數

下麵說說$dp$的思路：

$dp[i][j]$表示能用最多$j$次第$2$種操作能變成$a_i$的最小值

假設$a_k$所有可以用最多$j$次第$2$種操作能變成$i$的最小值，則$dp[i][j]=a_k$

舉個慄子：

3 1 4 

對於這個$4$來說，用最多$2$次操作能變成坐標為$3$的數最小值，就是$1$

如果能理解定義了，那我們接著往下看：

$dp$遞推其實並不難，取個$min$比較就行

統計答案怎麼做？

我們可以枚舉用了幾次$2$的操作，後直接相加$dp[1...n][j]$即可

這也是為什麼定義方程是“用了j次及以下”的關鍵qwqq

Code:

//From:201929
#include<bits/stdc++.h>
#define L long long
using namespace std;
L a[2005],dp[2005][2005];
int main()
{
    int n;
    L x;
    scanf("%d%lld",&n,&x);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    for(int i=1;i<=n;i++)
    {
        dp[i][0]=a[i];
        for(int j=1;j<n;j++)
        {
            int k=i-j;
            if(k<=0) k+=n;
            dp[i][j]=min(dp[i][j-1],a[k]);
        }
    }
    L minn=1e18+5;
    for(int i=0;i<n;i++)
    {
        L summ=x*i;
        for(int j=1;j<=n;j++) summ+=dp[j][i];
        minn=min(minn,summ);
    }
    printf("%lld",minn);
    return 0;
}