动态规划例——2012年NOIP普及组复赛第三题：摆花



动态规划例——2012年NOIP普及组复赛第三题：摆花

问题描述：让4个人筹10元钱，他们分别有的钱数为：2元， 5元，10元，15元

他们能出的钱数分别为：0-2元；0-5元；0-10元；0-10（15>10）元

问有多少种方案：135种

 

 

一、动态规划简介：

1、  来源于数学中分支：“运筹学”。

2、  它在解决一些最优化问题中是最高效的方法。

3、  在各级信息学竞赛中（NOIP，GDOI，NOI，IOI，ACM），使用频率最高的算法。

4、  并不是所有的问题都适合于用DP，问题必须满足一定的条件才可以用DP，下面通过一个实例来讨论使用DP需要满足的条件。

5、  因为它和递推有些相似，但又不完全相同，有人将此类方法看作是递推法的一种。

#include <iostream>
#include <cstring>
#define MOD 1000007
using namespace std;
int n, m, i, j, k;
int a[101], f[101][101];
int main() {
        cin>>n>>m;
memset(f, 0, sizeof(f));
f[0][0] = 1;
for(i = 1 ;i <= n ;i++) {
cin>>a[i];
}
for(i = 1 ;i <= n ;i++) {
for(j = 0;j <= m ;j++) {
                  for(k=0;k<=a[i]&&k<=j;k++)
                  {
                       f[i][j] = (f[i][j] + f[i-1][j-k]) % MOD;
                  }
}
}
cout<<f[n][m];
system(“pause”);
}

摆花

(flower.cpp/c/pas)

【问题描述】

    小明的花店新开张，为了吸引顾客，他想在花店的门口摆上一排花，共 m 盆。通过调查顾客的喜好，小明列出了顾客最喜欢的 n 种花，从 1 到 n 标号。为了在门口展出更多种花，规定第 i 种花不能超过 ai盆，摆花时同一种花放在一起，且不同种类的花需按标号的从小到大的顺序依次摆列。

    试编程计算，一共有多少种不同的摆花方案。

 

【输入】

输入文件 flower.in，共 2 行。

第一行包含两个正整数 n 和 m，中间用一个空格隔开。


第二行有 n 个整数，每两个整数之间用一个空格隔开，依次表示 a1、a2、……an。

 

【输出】

输出文件名为 flower.out。

输出只有一行，一个整数，表示有多少种方案。注意：因为方案数可能很多，请输出方案数对 1000007 取模的结果。

 

【输入输出样例 1】

flower.in

2 4

3 2

flower.out

2

 

【输入输出样例说明】

    有 2 种摆花的方案，分别是(1，1，1，2)，  (1，1，2，2)。括号里的 1 和 2 表示两种花，比如第一个方案是前三个位置摆第一种花，第四个位置摆第二种花。

 

【数据范围】

对于 20%数据，有  0<n≤8，0<m≤8，0≤ai≤8；

对于 50%数据，有 0<n≤20，0<m≤20，0≤ai≤20；

对于 100%数据，有 0<n≤100，0<m≤100，0≤ ai≤100。

【分析】

    设f[i,j]表示前i种花放在前j个花盆里的最大方案数，那么
f[i,j]=sum(f[i-1,j-x]) (0<=x<=min(a[i],j));
解释一下状态转移方程。前J个花盆里，第I种花最少放0个，最多放min（a[i],j）个
边界 :f[i,0]=1  (i>=0),   f[0,j]:=0  (j>0);
for(i=1 to n)
{
for(j=1 to m)
{
if (j<a[i])
  l=j;
                else
  l=a[i];
for(k=0 to l)
f[i,j]=(f[i,j]+f[i-1,j-k])mod 100007;
}
}
http://blog.163.com/lcf1974@126/blog/static/1238966012014224102125610/