UESTC 1692 这是一道比CCCC简单题更有想象力的中档题 完全背包

这是一道比CCCC简单题更有想象力的中档题 完全背包

Source

2017 UESTC Training for Dynamic Programming

UESTC 1692 这是一道比CCCC简单题更有想象力的中档题

My Solution

完全背包
dp[i][j][k]，已经考虑了前i个队员，写了j行代码，存在k个Bug的方案数，
通过递推顺序，第一维可以直接省略
if (k>=arr[i]) dp[j][k]=(dp[j][k]+dp[j-1][k-arr[i]])%mod;
//这行代码的实际含义是dp[i][j][k]=(dp[i-1][j][k]+dp[i][j-1][k-arr[i]]),
思考清楚为什么是这样的，尤其是为什么等式右边先是i-1，后面是i？
//转移方程似乎没有体现出一个队员可以写多份代码？
提醒：这里的递推顺序实际上是一个无穷背包的思想

时间复杂度 O(n*m*b)
空间复杂度 O(m*b)

#include 
#include 

using namespace std;
typedef long long LL;
const int MAXN = 5e2 + 8;

int a[MAXN];
LL dp[MAXN][MAXN], MOD;
inline LL mod(LL &x){
    x -= x / MOD * MOD;
}
int main()
{
    #ifdef LOCAL
    freopen("n.txt", "r", stdin);
    //freopen("n.out", "w", stdout);
    int T = 4;
    while(T--){
    #endif // LOCAL
    //ios::sync_with_stdio(false); cin.tie(0);

    int n, m, b, i, j, k;
    scanf("%d%d%d%d", &n, &m, &b, &i); MOD = i;
    for(i = 1; i <= n; i++){
        scanf("%d", &a[i]);
    }

    dp[0][0] = 1;
    for(i = 1; i <= n; i++){
        for(j = 1; j <= m; j++){
            for(k = 0; k <= b; k++){ if(k - a[i] >= 0) mod(dp[j][k] += dp[j-1][k-a[i]]);
            }
        }
    }
    LL ans = 0;
    for(k = 0; k <= b; k++){
        mod(ans += dp[m][k]);
    }
    cout << ans << "n";



    #ifdef LOCAL
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx