1223. 【2011.11.19模拟】统计蚂蚁(ants)
题目描述
蚂蚁山上有T(1<=T<=1,000)种蚂蚁，标记为1..T,每种蚂蚁有N_i只蚂蚁(1<=N_i<=100),现有A(A<=5000)只蚂蚁，从中选出S,S+1,…,B(1<=S<=B<=A)只蚂蚁一共有多少种选法？
如有5只蚂蚁分别为{1,1,2,2,3},一共有3种蚂蚁，每一种蚂蚁的数量分别为2，2，1，以下是选不同数量蚂蚁的方法：
1个蚂蚁3种选法:{1}{2}{3}
2个蚂蚁5种选法:{1,1}{1,2}{1,3}{2,2}{2,3}
3个蚂蚁5种选法:{1,1,2}{1,1,3}{1,2,2}{1,2,3}{2,2,3}
4个蚂蚁3种选法:{1,2,2,3}{1,1,2,2}{1,1,2,3}
5个蚂蚁1种选法:{1,1,2,2,3}
你的任务是从中选S..B只蚂蚁的方法总和。
输入
第一行: 4个空格隔开的整数: T, A, S和B；
第2到A+1行：每行一个整数表示蚂蚁的种类。
输出
输出从A只蚂蚁中选出S..B只蚂蚁的方法数，答案保留后6位。
样例输入
3 5 2 3 1 2 2 1 3
样例输出
10
题解，动态哈，还是有点难得，转移方程有点变态
f[i,j]:=f[i,j]+f[i-,j-0] +f[i-,j-1]…f[i-,j-k];
边界看题目哈，怎么来的自己想
const maxn=5000; var a:array[0..maxn,0..maxn] of longint; i,j,n,s,b,t,k,ans:longint; c:array[0..maxn] of longint; begin readln(t,n,s,b); fori:=1 to n do begin readln(j); inc(c[j]); end; fori:=0 to t do a[i,0]:=1; fori:=1 to t do forj:=1 to n do fork:=0 to c[i] do ifk<=j then a[i,j]:=(a[i,j]+a[i-1,j-k]) mod 1000000; fori:=s to b do ans:=(ans+a[t,i]) mod 1000000; writeln(ans mod 1000000); end.
