HDU 3602 2012(2010 ACM-ICPC Multi-University Training Contest（16）——Host by NUDT)

//dp[i]表示挣i块钱最少需要的座位数 //01背包的思想，大家可以这样想，对于每个船我们可选可不选，那么这样 //很明显就是一个01背包了。 #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int maxn = 1e4+10; const int INF = 0x3f3f3f3f; int dp[maxn], n, m, k; int cal(int x, int y){ //因此每个船的容量有限，因此我们需要特殊处理一下 int num = x/k + 1; if(x+y <= num*k) return x+y; //上一条船正好还有没有放满的位置可以放 else return num*k+y; //另外找一条新船来放 } int main(){ int T; scanf("%d", &T); while(T--){ scanf("%d%d%d", &n, &m, &k); memset(dp, INF, sizeof(dp)); dp[0] = 0; int a,b; while(n--){ scanf("%d%d", &a, &b); a++; for(int i = 1e4; i >= b; i--) if(dp[i-b] != INF) dp[i] = min(dp[i], cal(dp[i-b], a)); } int ans = 1e4; while(dp[ans] > k*m) ans--; printf("%d\n", ans); } return 0; }