uva 10154 Weights and Measures(01背包）

题目连接：10154 - Weights and Measures

题目大意：有若干只乌龟，每只乌龟有重量和负重两个属性，现在求这若干只乌龟最多可以叠多少层。

解题思路：01背包的变形， 以负重值作为背包的大小， 层数为所求dp值， 每次以min(当前可负重值-乌龟的重量, 乌龟的负重）考虑。

include <stdio.h>#include <string.h>#include <algorithm>using namespace std;const int N = 10005;int min(int a, int b) {return a > b ? b : a; }struct state {    int w;    int s;}tmp[N];int n, dp[N * 1000];bool cmp (const state& a, const state& b) {    return a.s > b.s;}void Init() {    n = 0;    memset(tmp, 0, sizeof(tmp));    memset(dp, 0, sizeof(dp));    while (scanf("%d%d", &tmp[n].w, &tmp[n].s) == 2)    n++;    sort(tmp, tmp + n, cmp);}int solve() {    int Max = tmp[0].s, t;    for (int i = 0; i < n; i++) {for (int j = tmp[i].w; j <= Max; j++) {    if (dp[j]) {t = min(j - tmp[i].w, tmp[i].s);if (dp[t] < dp[j] + 1)    dp[t] = dp[j] + 1;    }}t = tmp[i].s - tmp[i].w;if (dp[t] == 0)    dp[t] = 1;    }    int cur = 0;    for (int i = 0; i <= Max; i++) {if (cur < dp[i])    cur = dp[i];    }    return cur;}int main() {    Init();    printf("%d\n", solve());    return 0;}