1414 冰雕 51nod 暴力

1414 冰雕

题目来源： CodeForces

基准时间限制：1 秒空间限制：131072 KB 分值: 20 难度：3级算法题

关注

白兰大学正在准备庆祝成立256周年。特别任命副校长来准备校园的装扮。

校园的中心竖立着n个冰雕。这些雕像被排在一个等分圆上，因此他们形成了一个正n多边形。这些冰雕被顺针地从1到n编号。每一个雕有一个吸引力t[i].

校长来看了之后表示不满意，他想再去掉几个雕像，但是剩下的雕像必须满足以下条件：

· 剩下的雕像必须形成一个正多边形(点数必须在3到n之间，inclusive)，

· 剩下的雕像的吸引力之和要最大化。

请写一个程序帮助校长来计算出最大的吸引力之和。如果不能满足上述要求，所有雕像不能被移除。

Input

单组测试数据。

第一行输入一个整数n(3≤n≤20000),表示初始的冰雕数目。

第二行有n个整数t[1],t[2],t[3],…,t[n],表示每一个冰雕的吸引力(-1000≤t[i]≤1000)，两个整数之间用空格分开。

Output

输出答案占一行。

Input示例

8

1 2 -3 4 -5 5 2 3

6

1 -2 3 -4 5 -6

Output示例

14

9

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<sstream>

#include<algorithm>

#include<queue>

#include<deque>

#include<iomanip>

#include<vector>

#include<cmath>

#include<map>

#include<stack>

#include<set>

#include<fstream>

#include<memory>

#include<list>

#include<string>

using namespace std;

typedef long long LL;

typedef unsigned long long ULL;

#define MAXN 20009

#define N 21

#define MOD 1000000

#define INF 1000000009

const double eps = 1e-;

const double PI = acos(-1.0);

/*

注意到MAXN比较小，可以用暴力试一试

*/

int a[MAXN], ans, n;

int main()

{

    while (scanf("%d", &n) != EOF)

    {

        for (int i = ; i < n; i++)

            scanf("%d", &a[i]);

        ans = -INF;

        for (int i = ; i <= n / ; i++)//最少是正三角形，枚举顶点之间的间距，在1到n/3

        {

            if (n%i) continue;//无法通过去点组成该正多边形

            for (int j = ; j < i; j++)//枚举起点

            {

                int tmp = ;

                for (int k = j; k < n; k += i)//计算吸引力之和

                    tmp += a[k];

                ans = max(ans, tmp);

            }

        }

        printf("%d\n", ans);

    }

}

巴特西

1414 冰雕 51nod 暴力

最新文章

热门文章