# Colorful Slimes

+关注继续查看

### 题目描述

Snuke lives in another world, where slimes are real creatures and kept by some people. Slimes come in N colors. Those colors are conveniently numbered 1 through N. Snuke currently has no slime. His objective is to have slimes of all the colors together.

Snuke can perform the following two actions:

Select a color i (1≤i≤N), such that he does not currently have a slime in color i, and catch a slime in color i. This action takes him ai seconds.

Cast a spell, which changes the color of all the slimes that he currently has. The color of a slime in color i (1≤i≤N−1) will become color i+1, and the color of a slime in color N will become color 1. This action takes him x seconds.

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

Constraints

2≤N≤2,000

ai are integers.

1≤ai≤109

x is an integer.

1≤x≤109

### 输入

The input is given from Standard Input in the following format:

N x
a1 a2 … aN

### 输出

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

### 样例输入 Copy

2 10
1 100

12

### 提示

Snuke can act as follows:

Catch a slime in color 1. This takes 1 second.

Cast the spell. The color of the slime changes: 1 → 2. This takes 10 seconds.

Catch a slime in color 1. This takes 1 second.

#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize (2)
#pragma G++ optimize (2)
#include <bits/stdc++.h>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
#define wuyt main
typedef long long ll;
#define HEAP(...) priority_queue<__VA_ARGS__ >
#define heap(...) priority_queue<__VA_ARGS__,vector<__VA_ARGS__ >,greater<__VA_ARGS__ > >
template<class T> inline T min(T &x,const T &y){return x>y?y:x;}
template<class T> inline T max(T &x,const T &y){return x<y?y:x;}
ll read(){ll c = getchar(),Nig = 1,x = 0;while(!isdigit(c) && c!='-')c = getchar();
if(c == '-')Nig = -1,c = getchar();
while(isdigit(c))x = ((x<<1) + (x<<3)) + (c^'0'),c = getchar();
return Nig*x;}
const ll inf = 1e15;
const int maxn = 1e6 + 7;
const int mod = 1e9 + 7;
///ll n,m,k,x;
/**
ll superpow(ll a,ll b){
ll ans=1;
while (a>0)
{
if (a%2) ans=ans*b%n;
b=b%n*b%n;
a/=2;
}
return ans;
}**/
ll n,x;
ll num1[maxn],num2[maxn];
int main(){
for(int i=0;i<n;i++) num2[i]=inf;
///memset(num2,0x3f3f3f3f,sizeof(num2));
ll ans=inf;
for(int k=0;k<n;k++){
ll temp=k*x;
for(int i=0;i<n;i++)
num2[i]=min(num2[i],num1[(i-k+n)%n]);
for(int j=0;j<n;j++)
temp+=num2[j];
ans=min(ans,temp);
}
cout<<ans<<endl;
return 0;
}



ps:最小值设置为0x3f3f3f3f 本题不能通过

13308 0

20890 0

22279 0

14885 0

14710 0

20389 0
+关注
312

0

JS零基础入门教程（上册）