http://codeforces.com/contest/543/problem/A
一开始这题用了多重背包做，结果有后效性。
就是如果6，这样拆分成
1 + 2 + 3的，那么能产生3的就有两种情况了（同一种物品，两种情况，所以有了后效性）
分别是1 + 2 = 3和0 + 3 = 3
以前的多重背包只需要输出那些最优解，所以这个后效性可以忽略，但是现在是输出方案种类，所以不能忽视。
一开始的时候还以为他只能写b / per_bug个，因为最多b个bug，每个程序员写per_bug个。那么就是b / per_bug行。
所以觉得是多重背包。但是不是，第一，这里没限制它写多少行，确实是最多b / per_bug行，但是如果多了几行，也就是超过了背包容量，这其实和无限使用时一个意思的。
多重背包的都是最多能用c个，而且用了c + 1 个的话，还是没超过背包容量的，这才是多重背包。。
那么这么想，任何一个programmer，都可以写0...m行。
因为它能写m行，而这个m已经是背包容量的最大值了。所以就相当于完全背包了。
如果再选多个容量就超过了背包容量，那不会叠加上来的。这是完全背包的思想吧
那么设dp[m][b]表示前i个程序员，一共写了m行，有b个bug的情况。
对于每个程序员，都可以写0...m行，dp[m][b] += dp[m - 1][b - cost];
从自己写的m - 1行递推上来，就相当于写了m行了。
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #include <assert.h> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; #include <iostream> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <string> #include <conio.h> const int maxn = 500 + 20; struct node { int hang; int bug; node(int hh, int bb) : hang(hh), bug(bb) {} node() {} }a[maxn]; int w[maxn]; int val[maxn]; int dp[maxn][maxn]; void work() { int n, m, b, MOD; scanf("%d%d%d%d", &n, &m, &b, &MOD); for (int i = 1; i <= n; ++i) { scanf("%d", &w[i]); } dp[0][0] = 1; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { // if (j * w[i] > b) break; for (int k = w[i]; k <= b; ++k) { dp[j][k] += dp[j - 1][k - w[i]]; if (dp[j][k] >= MOD) dp[j][k] %= MOD; } } } int ans = 0; for (int i = 0; i <= b; ++i) { ans += dp[m][i]; if (ans >= MOD) ans %= MOD; } printf("%d ", ans); } int main() { #ifdef local freopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endif work(); return 0; }