Writing Code-Codeforces511C**

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

http://codeforces.com/problemset/problem/544/C

完全背包

dp[i][j]表示第i行有j个bug

#include<stdio.h>

#include<string.h>

#define N 550

int dp[N][N], a[N];

int main()

{

    int n, m, b, MOD;

    while(scanf("%d%d%d%d", &n, &m, &b, &MOD)!=EOF)

    {

        int i, j, k, w, sum=;

        memset(dp, , sizeof(dp));

        memset(a, , sizeof(a));

        for(i=; i<n; i++)

            scanf("%d", &a[i]);

        for(i=; i<=m; i++)

        {

            w = i*a[i];

            if(w<=b) dp[i][w] = ;

        }

        for(i=; i<n; i++)

        for(j=; j<m; j++)

        for(k=; k<=b; k++)

        {

            if(dp[j][k])

            {

                int x = j-, y = k + a[i];

                if(y<=b)

                {

                    dp[x][y] += dp[j][k];

                    dp[x][y] %= MOD;

                }

            }

        }

        for(i=; i<=b; i++)

        {

            sum += dp[m][i];

            sum %= MOD;

        }

        printf("%d\n", sum);

    }

    return ;

}