35 条题解
-
2
Spectre LV 10 @ 2017-11-09 11:42:31
zhangyq987 Orz
ml[i]表示从i位置往左走再回到i位置可获得的最大满足度；
mr[i]表示从i位置往右走再回到i位置可获得的最大满足度；C++代码
#include<iostream> using namespace std; #define INF 10000000 #define MAXN 1005 int n,l,r; int d[MAXN],f[MAXN],c[MAXN]; int ml[MAXN],mr[MAXN],sum[MAXN]; void init() { cin >>n>>l>>r; for(int i=1;i<=n;i++) cin >>d[i]; for(int i=1;i<=n;i++) cin >>f[i]; sum[0]=0; for(int i=1;i<=n;i++) cin >>c[i],sum[i]=sum[i-1]+c[i]; ml[0]=0;ml[n+1]=0; mr[0]=0;mr[n+1]=0; for(int i=1;i<=n;i++) ml[i]=max(ml[i-1]-l-r,0)+c[i]; for(int i=n;i>=1;i--) mr[i]=max(mr[i+1]-l-r,0)+c[i]; } int main() { ios::sync_with_stdio(0); init(); int ans=-INF,t; for(int i=1;i<=n;i++)//in { for(int j=1;j<=n;j++)//out { if(i<j) t=ml[i]+mr[j]+sum[j-1]-sum[i]-r*(j-i)-d[i]-f[j]; else if(i>j) t=mr[i]+ml[j]+sum[i-1]-sum[j]-l*(i-j)-d[i]-f[j]; else t=c[i]-d[i]-f[j]; ans=max(t,ans); } } cout <<ans<<endl; return 0; } -
2
zhangyq987 LV 8 @ 2009-08-23 23:03:54
var
d,c,f,ll,rr:packed array[0..1000]of longint;
s:packed array[0..1000]of int64;
n,l,r,i,j,max,k,t,p,last:longint;
begin
readln(n,l,r);max:=-maxlongint;
for i:=1 to n do read(d[i]);readln;
for i:=1 to n do read(f[i]);readln;
for i:=1 to n do begin read(c[i]);s[i]:=s+c[i];end;
for i:=1 to n do
begin
last:=0;
for j:=i-1 downto 1 do begin
p:=last+c[j]-l-r;
if p>ll[i] then ll[i]:=p;
last:=p;
end;
last:=0;if ll[i]rr[i] then rr[i]:=p;
last:=p;
end;
if rr[i]max then max:=k;
end;
end;
write(max);
end.
添加两个预处理数组ll，rr就可以秒杀
ll[i]表示从i位置往左走再回到[i]位置可获得的最大满足度；
rr[i]表示从i位置往右走再回到[i]位置可获得的最大满足度；
有处理完枚举就可以秒杀！
-_- -
2
silverlows LV 9 @ 2009-08-23 23:01:38
dp,秒杀！
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms核心部分：for i:=2 to n do begin
fillchar(f2,sizeof(f2),0);
f2[1]:=f1[6];
f2[2]:=max(f1[2],f1[3],f1[4],f1[5],-maxlongint)-r-l+c[i];
f2[3]:=max(f1[3],f1[5],-maxlongint,-maxlongint,-maxlongint)+d+c[i]-d[i]-l;
f2[4]:=max(f1[4],f1[5],-maxlongint,-maxlongint,-maxlongint)+c[i]+a-r-a[i];
f2[5]:=max(c[i]-d[i]-a[i],f1[5]+d+c[i]-d[i]-l+a-a[i]-r,-maxlongint,-maxlongint,-maxlongint);
f2[6]:=max(f2[1],f2[2],f2[3],f2[4],f2[5]);
f1:=f2;
end;
初始化：f1[1]:=-maxlongint;
f1[2]:=-maxlongint;
f1[3]:=-maxlongint;
f1[4]:=-maxlongint;
f1[5]:=c[1]-d[1]-a[1];
f1[6]:=max(f1[1],f1[2],f1[3],f1[4],f1[5]);
O(n)级算法 -
1
2490748374 LV 8 @ 2014-07-16 19:15:05
艹艹艹艹艹艹艹艹艹艹艹艹艹艹！！！！还有负数答案！！！
-
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms万恶的预处理...这题我拖了N长时间...
记得上次wa了一半.................
为啥今天心血来潮叫上去就秒杀呢.....PS：天啊~的日文版是
-
0
zhanghanyuan LV 10 @ 2009-09-11 19:09:17
好难理解的题意
-
0
181818181818 LV 10 @ 2009-09-01 21:33:56
silverlows的算法好奇怪哦
O(n^2)还是比较好想的。。
本菜突发奇想出一个O(n)算法，但是语文太差，表述不清。
Spectre
LV 10
@ 2017-11-09 11:42:31
