UVALive 6855 Banks （暴力）

Banks

题目链接：

http://acm.hust.edu.cn/vjudge/contest/130303#problem/A

Description

http://7xjob4.com1.z0.glb.clouddn.com/8ce645bf3da25e2731b2fea4c21a985b

Input

The input file contains several test cases, each of them as described below. On the first line, we have the number n of banks. On the second line, we have the capitals ki (n > i ≥ 0) of all banks, in the order in which they are found on Wall Street from Wonderland. Each capital is separated by a single whitespace from the next one, except for the final capital which is directly followed by the newline character.

Output

For each test case, the output contains a single line with the value of the minimal number of magic moves.

Sample Input

``` 4 1 -2 -1 3 ```

Sample Output

``` 9 ```

Source

2016-HUST-线下组队赛-4
##题意：给出一个循环序列，每次可以操作可以把一个负数取反成a，并把其周围的两个数减去a. 求最少次数使得结果序列非负.
##题解：如果序列能够达到全部非负的状态，那么无论先操作哪个数都是一样的次数. 所以直接暴力枚举所有负数，递归处理即可.
##代码： ``` cpp #include #include #include #include #include #include #include #include #include #include #include #define LL long long #define maxn 10100 #define inf 0x3f3f3f3f #define mod 1000000007 #define mid(a,b) ((a+b)>>1) #define eps 1e-8 #define IN freopen("in.txt","r",stdin); using namespace std;

int num[maxn];
int ans, n;

void dfs(int cur) {
if(num[cur] >=0) return ;
num[cur] = -num[cur]; ans++;
int l = cur - 1; if(l == 0) l = n;
int r = cur + 1; if(r == n+1) r = 1;
num[l] -= num[cur];
num[r] -= num[cur];
if(num[l] < 0) dfs(l);
if(num[r] < 0) dfs(r);
}

int main()
{
//IN;

while(scanf("%d", &n) != EOF)
{
    for(int i=1; i<=n; i++) {
        scanf("%d", &num[i]);
    }

    ans = 0;
    for(int i=1; i<=n; i++) {
        if(num[i] < 0) {
            dfs(i);
        }
    }

    printf("%d
", ans);
}

return 0;

}