题解 AT2042 【[AGC004B] Colorful Slimes】

Goodenough · 2020-03-02 14:38:13 · 题解

看到题解这么少，我来水一波。\ 实际上这是我们校内比赛赛题 我也是受了positive1巨佬的启发\ 就是用一个dp，dp[i][j]表示第i个点使用j及以下次魔法能达到的价格最小的那个点\ 注意long long

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const long long inf=0x3f3f3f3f3f3f3f3f;
long long n,x,a[2005],dp[2005][2005],sum,ans=inf;
int main(){
    scanf("%lld%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]);
        }
    }
    for(int i=0;i<n;i++){
        sum=x*i;
        for(int j=1;j<=n;j++)
            sum+=dp[j][i];
        ans=min(ans,sum);
    }
    printf("%lld",ans);
    return 0;
}

这就好了，想清楚了dp的内涵就没什么问题