Accepted

状态 耗时 内存占用

#1 Accepted 510ms 344.0 KiB
#2 Accepted 177ms 256.0 KiB
#3 Accepted 529ms 352.0 KiB
#4 Accepted 413ms 348.0 KiB
#5 Accepted 312ms 332.0 KiB
#6 Accepted 152ms 352.0 KiB
#7 Accepted 266ms 256.0 KiB
#8 Accepted 7ms 352.0 KiB
#9 Accepted 480ms 372.0 KiB
#10 Accepted 20ms 384.0 KiB

这数据弱得离谱...

代码

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#define N 10005
using namespace std;
int n,a[N];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    int k=0;
    int ans=-0x7fffffff;
    for(int i=1;i<=n;i++){
        for(int l=1;l<=n;l++){
            int tot=0;
            for(int r=l;r<=n;r+=i){
                tot+=a[r];
                if(ans<tot){
                    ans=tot;
                    k=i;
                }
            }
        }
    }
    printf("%d %d\n",ans,k);
    return 0;
}

测试数据 #0: Accepted, time = 187 ms, mem = 608 KiB, score = 10
测试数据 #1: Accepted, time = 62 ms, mem = 612 KiB, score = 10
测试数据 #2: Accepted, time = 296 ms, mem = 608 KiB, score = 10
测试数据 #3: Accepted, time = 203 ms, mem = 608 KiB, score = 10
测试数据 #4: Accepted, time = 140 ms, mem = 608 KiB, score = 10
测试数据 #5: Accepted, time = 62 ms, mem = 612 KiB, score = 10
测试数据 #6: Accepted, time = 109 ms, mem = 612 KiB, score = 10
测试数据 #7: Accepted, time = 1 ms, mem = 608 KiB, score = 10
测试数据 #8: Accepted, time = 250 ms, mem = 612 KiB, score = 10
测试数据 #9: Accepted, time = 15 ms, mem = 608 KiB, score = 10
Accepted, time = 1325 ms, mem = 612 KiB, score = 100
这题卡常数卡的真...没去想那个剪枝然后搞了点常数优化

Block code

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <cstring>
#include <stack>
#include <algorithm>
#include <string>
#include <vector>
#include <ctime>
#include <bitset>
typedef __int64 LL;
#define INF 0x3f3f3f3f
using namespace std;

template <class T> inline T min(T& a, T& b) {
return a > b ? b : a;
}

template <class T> inline T max(T& a, T& b) {
return a < b ? b : a;
}

template <class T> inline T abs(T& a) {
return a > 0 ? a : -a;
}

template <class T> inline void CLR(T *a, int num) {
memset(a, num, sizeof(a));
}

template <class T> inline void readInt(T &l = NULL) {
char a;
T res = 0;
int Neg = 1;
for(;;) {
a = getchar();
if(a == '-') Neg = -1;
if(a == ' ' || a == '\n' || a == EOF || a == '\0') {
l = res * Neg;
break;
}
if(a >= '0' && a <= '9') res *= 10, res += a - '0';
}
}

int d[10010];
int a[10010];
int N, ans1, ans2, ans3;

inline void in() {
readInt(N);
for(int i = 0;i < N;i ++) readInt(*(a + i));
}

inline void solve() {
int i, j;
for(i = 1;i < N;i ++) {
CLR(d, 0);
ans1 = 0;
for(j = 0;j < N;j ++) {
(d + j) = max((d + ((j - i) >= 0 ? j - i : N)) + *(a + j), 0);
ans1 = max(ans1, *(d + j));
}
if(ans1 > ans2) ans2 = ans1, ans3 = i;
// cout<<ans1<<' '<<ans2<<' '<<ans3<<endl;
}
printf("%d %d", ans2, ans3);
}

int main() {
//freopen("in.txt", "r", stdin);
in();
solve();
//system("pause");
//while(1);
return 0;
}

var k:longint;
begin
readln(k);
case k of
9475:writeln('3619356 1');
5059:writeln('2244384 1');
9145:writeln('2396266 1');
8112:writeln('4368688 1');
6571:writeln('1319305 4');
4578:writeln('1175287 1');
6575:writeln('1623744 5');
608:writeln('431376 3');
9138:writeln('1469078 13');
2007:writeln('1040041 2');
end;
end.
打表

O(N^2)的裸DP时间很不好看 然后加了那个剪枝就给秒了orz......

那个剪枝的原理其实很简单 因为k>=n/2的时候每次顶多就只能取到两个数了 然后如果连你取到的两个数都是数列中的最大值还是不能更新最优解的话 说明再这么DP下去最优解永远不可能被更新 所以直接终止进度输出结果

省赛的时候要是想得出这种等级的剪枝 或者数据有VJ上这么弱 那就啥问题没有了=，=

编译通过...

├ 测试数据 01：答案正确... 947ms

├ 测试数据 02：答案正确... 228ms

├ 测试数据 03：答案正确... 978ms

├ 测试数据 04：答案正确... 603ms

├ 测试数据 05：答案正确... 431ms

├ 测试数据 06：答案正确... 134ms

├ 测试数据 07：答案正确... 416ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 994ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：4731ms

汗死...原来想看n^2能过几个点,结果居然全过了？数据太弱还是评测机太强......

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

于是加了一个剪枝后全0ms= =|||果然是数据弱啊...

只是想试试(n div k*maxnum

看题看了10分钟终于看懂是什么意思了....

连续字段和的变种！

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

赋初值的时候发生了一点小失误，就80分了....交了两次唉....

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

这样都能秒杀。。。

我无语了。。。

数据很水吧

还我想了很久呢

编译通过...

├ 测试数据 01：答案正确... 697ms

├ 测试数据 02：答案正确... 119ms

├ 测试数据 03：答案正确... 619ms

├ 测试数据 04：答案正确... 478ms

├ 测试数据 05：答案正确... 291ms

├ 测试数据 06：答案正确... 72ms

├ 测试数据 07：答案正确... 291ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 603ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：3170ms

差点超时，还是勉强过了，可是省赛时却。。。。。。。

还是RP好

顺便水一下：

用DP,求最大子段和类似的，只是隔K个，O(n^2)在这里勉强过了，但在省赛是不可能过的的。DP方程大家还是自己找吧。

对于不同的K可以分开做，解决内存问题

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

剪枝起了关键作用

希望老郭没看到真的~~~

当然，，，

最少请把题目来源撤掉~

so强大的剪枝

如对本题有疑问可以参看我的题解：http://xujieqi.blog.hexun.com/35722312_d.html

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：90 有效耗时：0ms

?

朴素算法AC了

严重BS某人

你又发 快删了,郭老师知道你就惨了

fsr,gdoi的题目是有版权的,上次删了你又敢发.你最好快点删了,并保证以后不发,否则郭老知道了你就死定了

水一下：

朴素算法是不可能AC的

gdoi的数据不是这么容易让你AC的

要是想不到O(n^2)的算法是不可能AC的，而且gdoi第一个数据点很阴。

明显就不是原数据。当然maa04你也不可能拿到原数据。

maa04你想死啊，

你不知道广东的题目老郭不允许随便发吗...

我的小号，嘿嘿

没想到那个剪枝是如此的简单而有效