讨论 / 纠结了
ted 2013-08-02 22:35:00
点我顶贴 收藏 删除
状态: Unaccepted

测评机: Xeond[6]

得分: 90分

提交日期: 2011-11-8 21:07:00

有效耗时: 641毫秒

测试结果1: 通过本测试点|有效耗时94ms

测试结果2: 通过本测试点|有效耗时94ms

测试结果3: 测试结果错误.错误结果为:133457

正确结果应为:131294

测试结果4: 通过本测试点|有效耗时63ms

测试结果5: 通过本测试点|有效耗时62ms

测试结果6: 通过本测试点|有效耗时63ms

测试结果7: 通过本测试点|有效耗时78ms

测试结果8: 通过本测试点|有效耗时62ms

测试结果9: 通过本测试点|有效耗时63ms

测试结果10: 通过本测试点|有效耗时62ms

第3点为什么比正解大呢?

求教

var

t,tt,ans:int64;

l,i,n,a0,aa,bb,cc:longint;

a:array[0..1000000]of longint;

hash:array[-50000..50000]of longint;

function domax(l,r:longint):int64;

var

s,max:int64;

i:longint;

begin

s:=0;

max:=-1000000000000000000;

for i:=l to r do

begin

s:=s+a[i];

if s>max

then max:=s;

if s<0

then s:=0;

end;

domax:=max;

end;

procedure doit(y,x:longint);

var

t,tt:int64;

i:longint;

begin

ans:=-100000000000000000;

if y+y-x+1<=n

then begin

for i:=x to y do

a[i+y-x+1]:=a[i];

l:=y+y-x+1;

end

else begin

ans:=domax(0,n);

writeln(ans);

halt;

end;

t:=domax(0,l);

if t>ans

then ans:=t;

t:=0;

for i:=x to y do

t:=t+a[i];

t:=t*((n-(x-1))div(y-x+1));

tt:=t;

for i:=x to x+(n-(x-1))mod(y-x+1)-1 do

begin

tt:=tt+a[i];

if tt>t

then t:=tt;

end;

tt:=t;

for i:=x-1 downto 0 do

begin

tt:=tt+a[i];

if tt>t

then t:=tt;

end;

if t>ans

then ans:=t;

t:=0;

for i:=x to y do

t:=t+a[i];

t:=t*((n-(x-1))div(y-x+1)-1);

tt:=t;

for i:=x to x+(n-(x-1))mod(y-x+1)-1 do

begin

tt:=tt+a[i];

if tt>t

then t:=tt;

end;

tt:=t;

for i:=y downto 0 do

begin

tt:=tt+a[i];

if tt>t

then t:=tt;

end;

if t>ans

then ans:=t;

t:=0;

for i:=x to y do

t:=t+a[i];

t:=t*((n-(x-1))div(y-x+1)-2);

tt:=t;

for i:=x to y do

begin

tt:=tt+a[i];

if tt>t

then t:=tt;

end;

tt:=t;

for i:=y downto 0 do

begin

tt:=tt+a[i];

if tt>t

then t:=tt;

end;

if t>ans

then ans:=t;

writeln(ans);

halt;

end;

begin

read(n,a0,aa,bb,cc);

fillchar(hash,sizeof(hash),255);

hash[a0]:=0;

a[0]:=a0;

for i:=1 to n do

begin

a[i]:=(a[i-1]+aa+trunc(cc/2))*bb mod cc-trunc(cc/2);

if hash[a[i]]=-1

then hash[a[i]]:=i

else doit(i-1,hash[a[i]]);

end;

ans:=domax(0,n);

writeln(ans);

end.

#1 我为数学狂@2011-11-18 12:56:00
回复 删除
土方法

把数组的长度加一试试、、、

#2 柳暗花明@2013-08-02 22:35:00
回复 删除
133457!

这个数字我的结果中出现了好多次,都是错的。

状态: Unaccepted

测评机: Xeond[6]

得分: 20分

提交日期: 2013-8-2 22:32:00

有效耗时: 125毫秒

测试结果1: 通过本测试点|有效耗时78ms

测试结果2: 通过本测试点|有效耗时47ms

测试结果3: 测试结果错误.错误结果为:133457 正确结果应为:131294

测试结果4: 测试结果错误.错误结果为:133457 正确结果应为:438246

测试结果5: 测试结果错误.错误结果为:133457 正确结果应为:13482386

测试结果6: 测试结果错误.错误结果为:133457 正确结果应为:5937776

测试结果7: 测试结果错误.错误结果为:133457 正确结果应为:7798198116

测试结果8: 测试结果错误.错误结果为:133457 正确结果应为:192945859206

测试结果9: 测试结果错误.错误结果为:133457 正确结果应为:41738

测试结果10: 测试结果错误.错误结果为:133457 正确结果应为:129620623090

C语言码:求正解:

/*

* http://www.rqnoj.cn/Problem_649.html

* 题目:最大连续子序列和

*/

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <math.h>

#include <limits.h>

#define TABLE(a,b) table[a*n+b]

long A,B,C;

int n;

long* arr;

void get_result(int i)

{

if(i==n) return;

arr[i] = (long)(arr[i-1]+A+floor(C/2))*B % (long)C-floor(C/2);

get_result(i+1);

}

void main()

{

int i,j,k;

long a0;

long max=-LONG_MAX;

scanf("%d %ld %ld %ld %ld",&n,&a0,&A,&B,&C);

arr = (long*)calloc((n+1),sizeof(long));

long* table = (long*)calloc((n+1)*(n+1),sizeof(long));

if(arr == NULL || table == NULL) printf("1\n");

arr[0] = a0;

get_result(1);

TABLE(0,0) = 0;

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

{

TABLE(0,i) += arr[i];

}

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

{

for(j=i+1;j<n;j++)

{

TABLE(i,j) = TABLE(i,j-1) + arr[j];

if(TABLE(i,j) > max) max = TABLE(i,j);

}

}

printf("%ld",max);

free(arr);

free(table);

}

查看更多回复
提交回复