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;}