题解详见http://www.desgard.com/learning/2015/03/25/UESTC_567/
1 #include<iostream> 2 #include<cstdio> 3 #include<cstdlib> 4 #include<cstring> 5 #include<string> 6 #include<queue> 7 #include<algorithm> 8 #include<map> 9 #include<iomanip> 10 #include<climits> 11 #include<string.h> 12 #include<numeric> 13 #include<cmath> 14 #include<stdlib.h> 15 #include<vector> 16 #include<stack> 17 #include<set> 18 #define INF 1e7 19 #define MAXN 100010 20 #define maxn 1000010 21 #define Mod 1000007 22 #define N 1010 23 using namespace std; 24 typedef long long LL; 25 26 int T; 27 int kase = 1, n; 28 int e[2010]; 29 LL res, sum; 30 void run() 31 { 32 sum = 0; 33 scanf("%d", &n); 34 for (int i = 1; i <= n; ++i){ 35 scanf("%d", &e[i]); 36 e[i + n] = e[i]; 37 sum += e[i]; 38 } 39 e[0] = e[n]; 40 e[2 * n + 1] = e[1]; 41 printf("Case #%d:", kase++); 42 for (int i = 1; i <= n; ++i) { 43 LL ans = sum - e[i] < sum - e[i - 1] ? sum - e[i] : sum - e[i - 1]; 44 LL temp = 0; 45 for (int c = 0; c < n; ++c) { 46 temp += e[i + c]; 47 ans = min(ans, temp + sum - e[i + c + 1]); 48 } 49 temp = 0; 50 for (int c = 1; c < n; ++c) { 51 int j = i - c; 52 if (j <= 0) j += n; 53 temp += e[j]; 54 ans = min(ans, temp + sum - e[j - 1]); 55 } 56 printf(" %lld", ans); 57 } 58 puts(""); 59 } 60 61 int main() 62 { 63 cin >> T; 64 while (T--) 65 run(); 66 return 0; 67 }