/ Vijos / 题库 / 摆花 /

# 31 条题解

• @ 2019-08-07 14:51:16

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

``````#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;
}
``````
• @ 2021-08-30 06:48:56
``````#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;
}
``````
• @ 2018-08-08 19:08:31

兄弟们，这次是德邦来了！
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
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.

• @ 2016-09-30 13:36:44

题解：
```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]; } ```

• @ 2021-02-25 12:28:59

//多重背包

#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];
}

• @ 2016-09-29 13:52:16
• @ 2016-08-16 11:16:31
``````#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

• @ 2015-12-08 14:31:11

一开始想复杂了。其实就像个变形的背包问题。只需一个一维数组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;
}

• @ 2015-10-31 10:36:52

#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;
}

• @ 2015-08-30 15:25:13
• @ 2014-10-29 10:52:05

#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);
}

• @ 2014-10-13 16:44:38

简单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;
}

• @ 2015-04-08 21:27:35

这是记忆化搜索。。。不是dp

• @ 2014-07-20 08:34:23

测试数据 #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

• @ 2014-05-22 20:15:55

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

• @ 2013-11-08 15:42:46

编译成功

测试数据 #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
for i:=1 to n do
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.

• @ 2013-10-29 22:33:30

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
// 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.

• @ 2013-10-25 15:16:59

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

• @ 2013-10-24 20:08:46

测试数据 #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
for i:=1 to n do
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.

• @ 2013-10-09 21:38:21

其实这就是个普通的背包，一位背包秒之，注意取模= =，当初就是没去WA了
var
n,m,i,j,x,k:longint;
f:array[-100..200]of longint;
begin
fillchar(f,sizeof(f),0);
f[0]:=1;
for i:=1 to n do
begin
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.

• @ 2013-08-19 17:39:25

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

ID
1792

5

2554

804

31%

13