【codevs 1315】振花DP
2964 ワード
テーマ説明Description
明ちゃんの花屋が新しくオープンしたので、お客さんを引き付けるために、花屋の入り口に花を並べて、共にm鉢を作りたいと思っています.お客様の好みを調べることで、明ちゃんはお客様が一番好きなn種の花を1からnの番号にリストしました.入り口にもっと多くの花を展示するために、i番目の花はai鉢を超えてはならないことを規定し、花を振るときは同じ花を一緒に置いて、異なる種類の花は記号の小さい順に並べなければならない.
プログラミング計算を試して、全部で何種類の異なる花の案がありますか.
入力記述Input Description
合計2行を入力します.
最初の行には2つの正の整数nとmが含まれ、中間は1つのスペースで区切られています.
2行目にはn個の整数があり、2つの整数の間に1つのスペースで区切られ、a 1、a 2、......anの順に表される.
出力記述Output Description
出力は1行、整数で、シナリオがどれだけあるかを示します.注意:シナリオ数が多い場合がありますので、シナリオ数対100007の型取りの結果を出力してください.
サンプル入力Sample Input
サンプル出力Sample Output
データ範囲とヒントData Size&Hint
【入出力サンプル説明】
花を振る案は2種類あり、それぞれ(1,1,1,2),(1,1,2,2)である.括弧の中の1と2は2つの花を表し、例えば1つ目の案は前の3つの位置に1つ目の花を並べ、4つ目の位置に2つ目の花を並べます.
【データ範囲】
辛いのか弱いのか、きっと普及組の水題をだまして訪問したに違いない.
いくつかの花を段階にしてdpすればいいです
明ちゃんの花屋が新しくオープンしたので、お客さんを引き付けるために、花屋の入り口に花を並べて、共にm鉢を作りたいと思っています.お客様の好みを調べることで、明ちゃんはお客様が一番好きなn種の花を1からnの番号にリストしました.入り口にもっと多くの花を展示するために、i番目の花はai鉢を超えてはならないことを規定し、花を振るときは同じ花を一緒に置いて、異なる種類の花は記号の小さい順に並べなければならない.
プログラミング計算を試して、全部で何種類の異なる花の案がありますか.
入力記述Input Description
合計2行を入力します.
最初の行には2つの正の整数nとmが含まれ、中間は1つのスペースで区切られています.
2行目にはn個の整数があり、2つの整数の間に1つのスペースで区切られ、a 1、a 2、......anの順に表される.
出力記述Output Description
出力は1行、整数で、シナリオがどれだけあるかを示します.注意:シナリオ数が多い場合がありますので、シナリオ数対100007の型取りの結果を出力してください.
サンプル入力Sample Input
2 4
3 2
サンプル出力Sample Output
2
データ範囲とヒントData Size&Hint
【入出力サンプル説明】
花を振る案は2種類あり、それぞれ(1,1,1,2),(1,1,2,2)である.括弧の中の1と2は2つの花を表し、例えば1つ目の案は前の3つの位置に1つ目の花を並べ、4つ目の位置に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。
辛いのか弱いのか、きっと普及組の水題をだまして訪問したに違いない.
いくつかの花を段階にしてdpすればいいです
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int mod = 1000007;
int dp[233][233],a[233];
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i = 1;i <= n;i ++)
scanf("%d",&a[i]);
dp[0][0] = 1;
for(int i = 1;i <= n;i ++)
{
for(int k = 0;k <= a[i];k ++)
{
for(int j = k;j <= m;j ++)
dp[i][j] = (dp[i][j] + dp[i - 1][j - k]) % mod;
}
}
printf("%d",dp[n][m]);
return 0;
}