问一道编程题目,有pascal代码,但看不懂,农夫John的N(1≤N≤100,000)只奶牛站成了一排并且从1到N标号,他们在可能举行一项抗议,他们每个都有着一个乐观值Ai(-10,000≤Ai≤10,000).已知当一组奶牛乐涫
来源:学生作业帮助网 编辑:作业帮 时间:2024/06/25 20:38:06
![问一道编程题目,有pascal代码,但看不懂,农夫John的N(1≤N≤100,000)只奶牛站成了一排并且从1到N标号,他们在可能举行一项抗议,他们每个都有着一个乐观值Ai(-10,000≤Ai≤10,000).已知当一组奶牛乐涫](/uploads/image/z/12953288-56-8.jpg?t=%E9%97%AE%E4%B8%80%E9%81%93%E7%BC%96%E7%A8%8B%E9%A2%98%E7%9B%AE%2C%E6%9C%89pascal%E4%BB%A3%E7%A0%81%2C%E4%BD%86%E7%9C%8B%E4%B8%8D%E6%87%82%2C%E5%86%9C%E5%A4%ABJohn%E7%9A%84N%281%E2%89%A4N%E2%89%A4100%2C000%29%E5%8F%AA%E5%A5%B6%E7%89%9B%E7%AB%99%E6%88%90%E4%BA%86%E4%B8%80%E6%8E%92%E5%B9%B6%E4%B8%94%E4%BB%8E1%E5%88%B0N%E6%A0%87%E5%8F%B7%2C%E4%BB%96%E4%BB%AC%E5%9C%A8%E5%8F%AF%E8%83%BD%E4%B8%BE%E8%A1%8C%E4%B8%80%E9%A1%B9%E6%8A%97%E8%AE%AE%2C%E4%BB%96%E4%BB%AC%E6%AF%8F%E4%B8%AA%E9%83%BD%E6%9C%89%E7%9D%80%E4%B8%80%E4%B8%AA%E4%B9%90%E8%A7%82%E5%80%BCAi%28-10%2C000%E2%89%A4Ai%E2%89%A410%2C000%29.%E5%B7%B2%E7%9F%A5%E5%BD%93%E4%B8%80%E7%BB%84%E5%A5%B6%E7%89%9B%E4%B9%90%E6%B6%AB)
问一道编程题目,有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]