Var a:array[1..100] of qword;
f:array[-100..100,-100..100] of qword;
i,j,k,m,n:longint;
Begin
readln(n,m);
For i:=1 to n do read(a[i]);
f[0,0]:=1;
For i:=1 to n do
For j:=0 to m do
For k:=0 to a[i] do
Begin
F[i,j]:=f[i,j]+f[i-1,j-k];
f[i,j]:=f[i,j] mod 1000007;
End;
writeln(f[n,m]);
readln;
End.
代码很短
话说lx为毛是分组背包 不是叫多重包- - 竟然忘了Mod WA了两次

测试数据 #0: Accepted, time = 0 ms, mem = 984 KiB, score = 10
测试数据 #1: Accepted, time = 15 ms, mem = 980 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 980 KiB, score = 10
测试数据 #3: Accepted, time = 15 ms, mem = 988 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 984 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 984 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 980 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 980 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 984 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 984 KiB, score = 10

program flower;
var
f:array[-100..100,-100..100]of longint;
a:array[1..1000]of longint;
n,m,i,j,k:longint;
BEGIN
read(n,m);
for i:=1 to n do read(a[i]);
for i:=1 to n do
for j:=1 to m do begin
for k:=j-a[i] to j do inc(f[i,j],f[i-1,k]);
if j<=a[i] then inc(f[i,j]);
f[i,j]:=f[i,j] mod 1000007;
end;
writeln(f[n,m]);
END.

分组背包。。。。。。
VijosEx via JudgeDaemon2/13.6.5.0 via libjudge
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 508 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 512 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 508 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 512 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 508 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 508 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 508 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 512 KiB, score = 10
测试数据 #8: Accepted, time = 3 ms, mem = 508 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 508 KiB, score = 10
Accepted, time = 3 ms, mem = 512 KiB, score = 100
#include <iostream>
#include <cstring>

using namespace std;

#define PRIME 1000007
#define MAXN 101

int f[MAXN][MAXN];
int a[MAXN];
int n,m;

int main(){
cin>>n>>m;
for (int i=0;i++<n;) cin>>a[i];
memset(f,0,sizeof(f));
f[0][0]=1;
for (int i=0;i++<n;){
for (int j=0;j<=a[i];j++){
for (int h=j;h<=m;h++){
f[i][h]+=f[i-1][h-j];
f[i][h]%=PRIME;
}
}
}
cout<<f[n][m]<<endl;
return 0;
}

#include<fstream>
using namespace std;
const int N(108),MODN(1000007);
int a[N],f[N][N]={0};
int main()
{
ifstream cin("flower.in");
ofstream cout("flower.out");
int n,m;

cin>>n>>m;
for (int i=1;i<=n;i++) cin>>a[i];
for (int i=0;i<=a[1];i++) f[1][i]=1;
for (int i=2;i<=n;i++)
{
f[i][0]=1;
for (int j=1;j<=m;j++)
for (int k=0;k<=a[i];k++)
if (j-k>=0)
f[i][j]=(f[i][j]+f[i-1][j-k])%MODN;
}
cout<<f[n][m]<<endl;
return 0;
}

这个。。。感谢石哲宇神牛！！！！！！！！！

（此程序是石大牛的）

program flower;

var

f:array[-100..100,-100..100] of longint;

a,b,c,d,n,m,i,j,k:longint;

s:array[1..100] of longint;

begin

fillchar(f,sizeof(f),0);

fillchar(s,sizeof(s),0);

read(n,m);

for a:=1 to n do

read(s[a]);

for a:=0 to n do

f[a,0]:=1;

for i:=1 to n do

for j:=1 to m do

begin

k:=s[i];

if j

├ 测试数据 01：答案正确... (14ms, 836KB)

├ 测试数据 02：答案正确... (0ms, 836KB)

├ 测试数据 03：答案正确... (15ms, 836KB)

├ 测试数据 04：答案正确... (15ms, 836KB)

├ 测试数据 05：答案正确... (12ms, 836KB)

├ 测试数据 06：答案正确... (15ms, 836KB)

├ 测试数据 07：答案正确... (0ms, 836KB)

├ 测试数据 08：答案正确... (15ms, 836KB)

├ 测试数据 09：答案正确... (15ms, 836KB)

├ 测试数据 10：答案正确... (15ms, 836KB)

---|---|---|---|---|---|---|---|-

Accepted / 100 / 121ms / 836KB

动态规划

数组要开到[-100..100,-100..100]

边界条件f=0

DP方程f:=f+f

注意a[i]的边界限制

注意取模

program flower;

var

f:array[-100..100,-100..100] of longint;

a,b,c,d,n,m,i,j,k:longint;

s:array[1..100] of longint;

begin

fillchar(f,sizeof(f),0);

fillchar(s,sizeof(s),0);

read(n,m);

for a:=1 to n do

read(s[a]);

for a:=0 to n do

f[a,0]:=1;

for i:=1 to n do

for j:=1 to m do

begin

k:=s[i];

if j

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
int ai[110];
int dp[110];
int main (){

//freopen("flower.in","r",stdin);
//freopen("flower.out","w",stdout);
int n,m;
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++) {
scanf("%d",&ai[i]);
}
dp[0]=1;
for(int j=1;j<=n;j++){//j种类
for(int i=m;i>=1;i--){//i盆数
for(int k=1;k<=ai[j];k++){//k：第j种植物的盆数
if(i-k>=0)
dp[i]=(dp[i]%1000007+dp[i-k]%1000007)%1000007;
else break;
}
}
}
printf("%d",dp[m]%1000007);
return 0;
}

组合数学解法：生成函数。
对于每个a[i]，生成一个母函数(x^0+x^1+...+x^a[i])
所有n个母函数的积的多项式展开的x^m的系数即为答案。
时间复杂度O(n m^2)

例如：n=3, m=7
a[1]=4, a[2]=5, a[3]=6
(x^0+x^1+...+x^4) (x^0+x^1+...+x^5) (x^0+x^1+...+x^6)
的展开的x^7系数为26，26即为答案。

#include<cstdio>
#include<cstring>

const int maxm=105;
const long long md=1000007;
int n,m,t;

struct F
{
    long long a[maxm];
    F() {memset(a,0,sizeof a);}
    F operator * (const F & x) const 
    {
        F ans;
        for (int i=0;i<=m;i++)
            for (int j=0;j<=i;j++)
                ans.a[i]=(ans.a[i]+a[j]*x.a[i-j])%md;
        return ans;
    }
}ANS;

    F make(int x)
    {
        F ans;
        for (int i=0;i<=x;i++) ans.a[i]=1;
        return ans;
    }

int main()
{
    ANS.a[0]=1;
    scanf("%d%d",&n,&m);
    for (int i=0;i<n;i++)
    {
        scanf("%d",&t);
        ANS=ANS*make(t);
    }
    printf("%d",ANS.a[m]);
    return 0;
}

dp【n】表示在n有几种方案

var a,z,dp:array[0..200]of int64;
n,m,s,d,f:longint;
begin
read(n,m);
for s:=1 to n do
read(a[s]);
dp[0]:=1;
for d:=1 to n do
begin
fillchar(z,sizeof(z),0);
for s:=0 to m do
for f:=s+1 to s+a[d] do
z[f]:=(z[f]+dp[s])mod 1000007;
for s:=1 to m do
dp[s]:=(dp[s]+z[s])mod 1000007;
end;
writeln(dp[m]);
end.

var
n:longint;
f:array[1..100,1..100]of longint;
a,s:array[0..100]of longint;
i,j,k:longint;
function min(i,j:longint):longint;
begin
if i<j then min:=i
else min:=j;
end;

begin
readln(n);
for i:=1 to n do
read(a[i]);
for i:=1 to n do
s[i]:=s[i-1]+a[i];

fillchar(f,sizeof(f),$7f div 3);
for i:=1 to n do
f[i,i]:=0;

for i:=n downto 1 do
for j:=i+1 to n do
for k:=i to j-1 do
f[i,j]:=min(f[i,j],f[i,k]+f[k+1,j]+s[j]-s[i-1]);
writeln(f[1,n]);
end.