CodeForces 543A - Writing Code DP 完全背包

有n个程序,这n个程序运作产生m行代码,但是每个程序产生的BUG总和不能超过b,

给出每个程序产生的代码,每行会产生ai个BUG,问在总BUG不超过b的情况下,

我们有几种选择方法思路:看懂了题意之后就是一个完全背包题了

定义dp[ i ][ j ][ k ] 表示前 i 个程序员,已经写了 j 行代码,

已经产生了 k 个 bugs 。

根据题意,得知第 i 个程序员会写 r 行代码,那么相当于

dp[ i ][ j ][ k ] += dp[i - 1][j - r][k - ra[ i ]]

Source Code:

/*************************************************************************
> File Name: code03.cpp
> Author: Jeremy Wu
> Created Time: Sun 31 May 2015 02:37:07 PM CST
************************************************************************/ #include <iostream> using namespace std; const int N = ;
int a[N];
int dp[][N][N]; int main () {
int i, j, k, l, m, n, bl, bugs, md; cin >> n >> bl >> bugs >> md;
for (i = ; i < n; ++i) cin >> a[i];
dp[][][] = ; for (int it = ; it <= n; ++it) {
i = it & ;
for (j = ; j <= bl; ++j) {
for (k = ; k <= bugs; ++k) {
dp[i][j][k] = dp[i ^ ][j][k];
if (j > && k >= a[it - ]) {
dp[i][j][k] += dp[i][j - ][k - a[it - ]];
}
while (dp[i][j][k] >= md) {
dp[i][j][k] -= md;
}
}
}
} int ans = ;
for (i = ; i <= bugs; ++i) {
ans += dp[n & ][bl][i];
while (ans >= md) {
ans -= md;
}
}
cout << ans << endl; return ;
}
上一篇:iOS 头文件导入@class注意事项


下一篇:文件路径获取 + 绝对路径 + 相对路径