测评机： 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.
这个数字我的结果中出现了好多次，都是错的。
状态: 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);
}