AGC004B Colorful Slimes

$ {\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#define L long longusing 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;}