107
2023-08-07 07:17
admin菲波那契数列 pascal !
var num:array[1..20]of integer;
i,m:integer;
begin
while not eof do
begin
num[1]:=1;
num[2]:=1;
for i:=3 to n do
num[i]:=num[i-1]+num[i-2];
writeln(num[n]);
end;
end.
pascal数字环
我的想法是用最大连续子段和算法在环上做n次，总复杂度为O(n^2)，考虑到n<=1000的复杂度，应该可以在1s内出解。以下是我写的程序：
Program dp;
Var
f, a: Array[0 .. 1000] Of longint; //a[]记录环上的数字，f[k]表示以k结尾的序列对应的最大子段和
max, i, j, k, n: longint;
Begin
Readln(n);
max := -maxint;
For i := 0 To n - 1 Do
Begin
Read(a[i]);
If a[j] > max Then max := a[j]; //这样处理可以在动规时省去对长度为1的序列的判断
End;
//初始化
For j := 0 To n - 1 Do //选择起点j，拆环为链
Begin
f[j] := a[j];
For i := j To j + n - 2 Do
Begin
k := (i + 1) Mod n;
f[k] := a[k];
If f[i Mod n] > 0 Then Inc(f[k], f[i Mod n]);
//状态转移
If f[k] > max Then max := f[k]; //更新最大值
End;
End;
Writeln(max);
End .