华师一附中OI组

标题: NOIP2012普及组第三题摆花 TYVJ2069 [打印本页]

作者: diggersun 时间: 2015-11-3 19:39
标题: NOIP2012普及组第三题摆花 TYVJ2069
描述
小明的花店新开张，为了吸引顾客，他想在花店的门口摆上一排花，共 m 盆。通过调查顾客的喜好，小明列出了顾客最喜欢的 n 种花，从 1 到 n 标号。为了在门口展出更多种花，规定第 i 种花不能超过 ai 盆，摆花时同一种花放在一起，且不同种类的花需按标号的从小到大的顺序依次摆列。
试编程计算，一共有多少种不同的摆花方案。
输入格式
第一行包含两个正整数 n 和 m，中间用一个空格隔开。
第二行有 n 个整数，每两个整数之间用一个空格隔开，依次表示 a1、a2、……an。
输出格式
输出只有一行，一个整数，表示有多少种方案。注意：因为方案数可能很多，请输出方案数对 1000007 取模的结果。
测试样例1
输入
2 4
3 2
输出
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。NOIP 2012

作者: diggersun 时间: 2015-11-3 19:40
非常好理解的dfs做法

#include <iostream>
using namespace std;
int a[100];
int c[100];
int n,m,i,s;
void dfs(int i)
{
int j,k;
if (i>=m)
{
s++;
for (j=0; j<=m-1; j++) cout<<a[j];cout<<endl;
}
else for (k=((i==0)?0:a[i-1]); k<=n-1; k++)
if (c[k]>0)
{
a[i]=k;
c[k]--;
dfs(i+1);
c[k]++;
}
}
int main()
{
cin>>n>>m;
for (i=0; i<=n-1; i++) cin>>c[i];
dfs(0);cout<<s%1000007;
return 0;
}

复制代码

作者: diggersun 时间: 2015-11-3 19:41
本帖最后由 diggersun 于 2015-11-4 19:46 编辑

有点技巧的DP做法
其实这种简单的DP可以认为是递推，因为排列的顺序是由小到大的，那么用 a（x，y）表示第X个位置放上满了第Y种花，或者说Y种花摆满X个位置的所有可能情况，那么
a（x-1，y-1）就是y-1种花摆满x-1个位置，我们最后在x位置摆上第Y种花就可以得到 A（x y）
a（x-2，y-1）就是y-1种花摆满x-2个位置，我们最后在x-1和x位置摆上第Y种花就可以得到 A（x y）当然第y种花要有2颗可以选择
****
然后累加。

#include <iostream>
#include <iomanip>
using namespace std;
int a[101][101];
int c[101];
int n,m,i,j,k,s;
int main()
{
cin>>n>>m;
for (i=1; i<=n; i++) cin>>c[i];
//for (i=0; i<=n; i++) a[i][0]=1;
a[0][0]=1;
for (i=1; i<=n; i++)
for (j=0; j<=m; j++)
for (k=0; k<=c[i]; k++)
if (j-k>=0) a[j][i]=(a[j][i]+a[j-k][i-1]);
for (i=0; i<=n; i++)
{for (j=0; j<=m; j++) cout<<setw(3)<<a[j][i];
cout<<endl;}
cout<<a[m][n];
return 0;
}

复制代码

欢迎光临华师一附中OI组 (http://hsyit.cn/)