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<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; }