讨论 / DP版pascal参考代码+注释,绝对简洁
xxt 2014-05-29 16:55:36
点我顶贴 收藏 删除
DP,多重背包变形

program flower;

var

n,m,i,j,k:longint;

a:array[1..100] of longint;;//表示第i种花最多摆多少盆

f:array[1..100,0..100] of longint;//前i种花摆j盆的方案数,注意要开0空间(一盆都不摆的情况)

begin

readln(n,m);

for i:=1 to n do

read(a[i]);

for i:=0 to a[1] do//只选第一种花,摆i盆的方案数(初始化操作)

f[1,i]:=1;

for i:=2 to n do//枚举花的种数(从第二盆开始)

for j:=0 to m do//枚举可摆的盆数

for k:=0 to a[i] do//枚举第i种花的盆数

if j>=k then f[i,j]:=(f[i,j]+f[i-1,j-k]) mod 1000007;//如果能摆k种花,总数就加上这部分(第i种摆k盆,前i-1种只能摆j-k盆

writeln(f[n,m]);//输出答案

end.

补充:(a+b) mod c=a mod c+b mod c,所以再加的过程mod就行了

查看更多回复
提交回复