题目描述
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
样例输出 Copy
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 comment(linker, "/stack:200000000") #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;} #define read read() 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(){ n=read,x=read; for(int i=0;i<n;i++) num1[i]=read; 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 本题不能通过
