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