作业帮问一道编程题目,有pascal代码,但看不懂,农夫John的N(1≤N≤100,000)只奶牛站成了一排并且从1到N标号,他们在可能举行一项抗议,他们每个都有着一个乐观值Ai(-10,000≤Ai≤10,000).已知当一组奶牛乐涫
来源：学生作业帮助网 编辑：作业帮 时间：2024/11/18 00:15:05
问一道编程题目,有pascal代码,但看不懂,农夫John的N(1≤N≤100,000)只奶牛站成了一排并且从1到N标号,他们在可能举行一项抗议,他们每个都有着一个乐观值Ai(-10,000≤Ai≤10,000).已知当一组奶牛乐涫
问一道编程题目,有pascal代码,但看不懂,
农夫John的N(1≤N≤100,000)只奶牛站成了一排并且从1到N标号,他们在可能举行一项抗议,他们每个都有着一个乐观值Ai(-10,000≤Ai≤10,000).
已知当一组奶牛乐涫值合为负数就可能发生暴动,于是John决定建立一些隔板将奶牛分组,请问有多少种合法分组方法.
Input
第1行：包含一个整数N
第2~n+1行：每行一个整数,依次描述奶牛1到奶牛n的乐观值
Output
一行仅包含一个数即分组方法数mod 1,000,000,009的结果
Sample Input
4
2
3
-3
1
Sample Output
4
标程：
const
\x05maxn=100055;
\x05mn=1000000009;
var
\x05num,a,s,f:array[0..maxn]of longint;
\x05n,m,i,wei,sum:longint;
procedure sort(l,r:longint);
var
tl,tr,mid,t:longint;
begin
tl:=l; tr:=r; mid:=num[(tl+tr) shr 1];
repeat
while num[tl]mid do dec(tr);
if tltr;
if tll then sort(l,tr);
end;
procedure prep;
begin
\x05 assign(input,'protest.in');reset(input);
\x05 assign(output,'protest.out');rewrite(output);
\x05 readln(n);
\x05 num[n+1]:=0;
\x05 for i:=1 to n do
\x05 begin
\x05\x05 read(a[i]);
\x05\x05 s[i]:=s[i-1]+a[i];
\x05\x05 num[i]:=s[i];
\x05 end;
\x05 sort(1,n+1); m:=1;
\x05 for i:=2 to n+1 do
if num[i]num[i-1] then
begin
inc(m); num[m]:=num[i];
end;
end;
function get(key:longint):longint;
var
\x05 l,r,mid\x05:longint;
begin
\x05 l:=1;r:=m;
\x05 while lkey then r:=mid-1
\x05\x05\x05else l:=mid+1;
\x05 end;
end;
function find(key:longint):longint;
var
\x05 ss:longint;
begin
\x05 ss:=0;
\x05 while key>0 do
\x05 begin
\x05\x05 ss:=(ss+f[key]) mod mn;
\x05\x05 key:=key-(key and (-key));
\x05 end;
\x05 exit(ss);
end;
procedure ini(key,nu:longint);
begin
\x05 while key
问一道编程题目,有pascal代码,但看不懂,农夫John的N(1≤N≤100,000)只奶牛站成了一排并且从1到N标号,他们在可能举行一项抗议,他们每个都有着一个乐观值Ai(-10,000≤Ai≤10,000).已知当一组奶牛乐涫
这个题目比较简单,是一个DP+优化
我们用f[i]表示将前i头牛划分成若干组的方案总数,用s[i]表示前i头牛的乐观值之和,那么就有
f[i]:=sum(f[k])其中1=0这个条件上,我们先对s进行排序,问题转化为对于给定的i,求出s[k]