一维数组降低空间复杂度。

#include <iostream>

using namespace std;

int n,m;
int dp[100000]={0};

int main()
{
    cin>>n>>m;
    int i,j,a;
    dp[0]=1;
    while(n>0)
    {
        n--;
        cin>>a;
        for(i=m;i>0;i--)
        {
            for(j=1;j<=a;j++)
            {
                if(i-j>=0)
                {
                    dp[i]+=dp[i-j];
                }
            }
            dp[i]=dp[i]%1000007;
        }
    }
    cout<<dp[m]<<endl;
    return 0;
}

#include<bits/stdc++.h>
using namespace std;

const int maxn=105, mod=1000007;
int n,m,a[maxn],f[2][maxn],t;
int main()
{
    cin>>n>>m;
    for(int i=1; i<=n; i++)
        cin>>a[i];
    f[0][0] = 1;
    for(int i=1; i<=n; i++){
        t = 1-t;
        for(int j=0; j<=m; j++){
            f[t][j] = 0;
            for(int k=0; k<=min(j, a[i]); k++)
              f[t][j] = (f[t][j] + f[1-t][j-k])%mod;
        }
    }
    cout<<f[t][m];
    return 0;
}

兄弟们，这次是德邦来了！
program baihua;
var
f:array[0..1000,0..1000] of longint;
a:array[1..1000] of longint;
m,n,k,i,j,l:longint;
begin
read(n,m);
for i:=1 to n do read(a[i]);
for i:=0 to n do f[i,0]:=1;
for i:=1 to n do
for j:=1 to m do
begin
if j<a[i] then l:=j else l:=a[i];
for k:=0 to l do
f[i,j]:=(f[i,j]+f[i-1,j-k]) mod 1000007;
end;
write(f[n,m]);
end.

题解：
c++
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cmath>
#include<cstring>
#include<string>
#include<iomanip>
using namespace std;
int a[101];
int f[101][101];
int main(int argc, char *argv[])
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
memset(f,0,sizeof(f));
for(int i=0;i<=a[1];i++) f[1][i]=1;
for(int i=2;i<=n;i++)
for(int j=0;j<=m;j++)
for(int k=0;k<=a[i];k++)
if(j>=k)
f[i][j]=(f[i][j]+f[i-1][j-k])%1000007;
cout<<f[n][m];
}


//多重背包

#include<bits/stdc++.h>
using namespace std;
int a[102];
int f[10002];
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
f[0]=1;
for(int i=1;i<=n;i++)
{
for(int j=m;j>=1;j--)
{
for(int k=1;k<=a[i];k++)
{
if(j-k<0)break;
f[j]=(f[j]+f[j-k])%1000007;
}
}
}
cout<<f[m];
}

http://blog.csdn.net/ocacs1/article/details/52701230
题解不谢

#include <bits/stdc++.h>
using namespace std;
int a[105],dp[105], n, m;
int main(){
    scanf("%d %d", &n, &m);
    for(int i=1; i<=n; i++)
        scanf("%d", &a[i]);
    memset(dp,0,sizeof(dp));
    dp[0] = 1;
    for(int i=1; i<=n; i++)
        for(int j=m; j>=0; j--)
            for(int k=1; k<=min(a[i],j); k++)
                dp[j] = (dp[j]+dp[j-k])%1000007;
    printf("%d", dp[m]%1000007);
}

DFS有毒，会完美TLE

一开始想复杂了。其实就像个变形的背包问题。只需一个一维数组f，f[i]表示放i盆花的方案数。之所以这样做是因为题目规定要按编号次序摆放，也就是说依次递推即可。上代码：

#include <stdio.h>
int limit[200];
int f[200];
int main(){
int n, m, i, j, k;
scanf("%d %d", &n, &m);
for(i=1; i<=n; i++)
scanf("%d", &limit[i]);
for(i=0; i<=m; i++)
f[i] = 0;
f[0] = 1;
for(i=1; i<=n; i++){ //枚举种类
for(j=m; j>=0; j--){ //枚举总共摆了多少
for(k=1; k<=limit[i] && j>=k; k++) //枚举这种花摆几盆
f[j] = (f[j]+f[j-k])%1000007;
}
}
printf("%d\n", f[m]%1000007);
return 0;
}

#include<iostream>
using namespace std;
const int MAXN = 100 + 10;
const int mod = 1000007;

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

int main()
{
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++)
for(int j=0; j<=m; j++)
for(int u=0; u<=a[i]; u++)
if(j-u >= 0)

f[i][j] = (f[i][j] + f[i-1][j-u])%mod;
cout<<f[n][m]<<endl;
return 0;
}

解题报告：
http://blog.csdn.net/onlynagesha/article/details/47949819

#include<stdio.h>
#include<algorithm>
using namespace std;
long long a[105],l[105],b[205][205],n,m,max1,ans;
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
int jj=0,jm=m;

b[0][0]=1;
for(int i=0;i<=m;i++)
for(int j=0;j<=n;j++)
for(int k=j+1;k<=m;k++)
for(int g=1;g<=a[k]&&g+i<=m;g++)
b[i+g][k]=(b[i+g][k]+b[i][j])%1000007;
for(int i=1;i<=n;i++)
ans=(ans+b[m][i])%1000007;
printf("%d",ans);
}

简单dp

P1792摆花
Accepted

记录信息

评测状态 Accepted
题目 P1792 摆花
递交时间 2014-10-13 16:43:35
代码语言 C++
评测机 上海红茶馆
消耗时间 60 ms
消耗内存 640 KiB
评测时间 2014-10-13 16:43:36

评测结果

编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 632 KiB, score = 10

测试数据 #1: Accepted, time = 0 ms, mem = 640 KiB, score = 10

测试数据 #2: Accepted, time = 0 ms, mem = 640 KiB, score = 10

测试数据 #3: Accepted, time = 15 ms, mem = 636 KiB, score = 10

测试数据 #4: Accepted, time = 0 ms, mem = 640 KiB, score = 10

测试数据 #5: Accepted, time = 0 ms, mem = 632 KiB, score = 10

测试数据 #6: Accepted, time = 0 ms, mem = 636 KiB, score = 10

测试数据 #7: Accepted, time = 15 ms, mem = 640 KiB, score = 10

测试数据 #8: Accepted, time = 15 ms, mem = 636 KiB, score = 10

测试数据 #9: Accepted, time = 15 ms, mem = 636 KiB, score = 10

Accepted, time = 60 ms, mem = 640 KiB, score = 100

代码

#include <iostream>
#include <cmath>
#include <stdio.h>
#include <algorithm>

using namespace std;

int n , m;
int i;
int a[100 + 2];
long long f[100 + 2][100 + 2];
const int modd = 1000007;

int dp( int i , int j )
{
if( i == n )
return 0;
if( j == m )
return 0;
if( f[i][j] != 0 )
return f[i][j];
int l;
long long ans = 0;
for( l = 0 ; l <= a[i] ; l++ )
if( j + l < m )
ans = ( ans + dp( i + 1 , j + l ) ) % modd;
else if( j + l == m )
ans++;
f[i][j] = ans;
return ans;
}

int main()
{
while( scanf( "%d %d" , &n , &m ) != EOF )
{
for( i = 0 ; i < n ; i++ )
scanf( "%d" , &a[i] );
cout << dp( 0 , 0 ) << endl;
}
return 0;
}

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

c++中答案数组要用long，不能用int，不然拿数据手测能过，交就只有70分了

编译成功

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

Accepted, time = 15 ms, mem = 828 KiB, score = 100

Code:
var
i,j,k,n,m:longint;
a,f:array[0..100]of longint;
begin
readln(n,m);
for i:=1 to n do
read(a[i]);
f[0]:=1;
for i:=1 to n do
for j:=m downto 1 do
for k:=1 to a[i] do
if j>=k then
f[j]:=(f[j]+f[j-k])mod 1000007;
write(f[m]);
end.

var a:array[0..100,0..100] of longint;
b:array[0..100] of longint;
i,j,k,l,q,w,e,n,m,s:longint;
function max(x,y:longint):longint;
begin
if x>y then exit(x) else exit(y);
end;
begin
readln(n,m); fillchar(a,sizeof(a),0);
// for i:=1 to n do b[i]:=100;
for i:=1 to n do read(b[i]);
for i:=0 to b[1] do a[1,i]:=1;
for i:=2 to n do
begin
for j:=0 to m do
begin
for k:=max(0,j-b[i]) to j do a[i,j]:=a[i-1,k]+a[i,j];a[i,j]:=a[i,j] mod 1000007;end;
end;
writeln(a[n,m]);
end.

学习了。这题的去模要很注意啊。不可以到最后再取！！

测试数据 #0: Accepted, time = 0 ms, mem = 864 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 868 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 860 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 864 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 864 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 864 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 860 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 860 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 864 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 860 KiB, score = 10
Accepted, time = 0 ms, mem = 868 KiB, score = 100
**********************************晒程序***************************************
Program p1792;
var n,m,i,j,k:longint;
a:array[1..100] of longint;
f:array[0..100,0..100] of longint;
Begin
readln(n,m);
for i:=1 to n do
read(a[i]);
fillchar(f,sizeof(f),0);
f[0,0]:=1;
for i:=1 to n do
for j:=0 to m do
for k:=0 to a[i] do
if j-k>=0 then
f:=(f+f) mod 1000007
else break;
writeln(f[n,m]);
end.

其实这就是个普通的背包，一位背包秒之，注意取模= =，当初就是没去WA了
var
n,m,i,j,x,k:longint;
f:array[-100..200]of longint;
begin
readln(n,m);
fillchar(f,sizeof(f),0);
f[0]:=1;
for i:=1 to n do
begin
read(x);
for j:=m-1 downto 0 do
if(f[j]>0)then
for k:=1 to x do
begin
inc(f[j+k],f[j]);
f[j+k]:=f[j+k] mod 1000007;
end;
end;
writeln(f[m]);
end.

哦，老天，想着longint够大，所以只有在最后才mod1000007，搞到错了n次，小心，每次做和后都要mod...