HDU2955 动态规划一维状态一维转移

这题囧了，看完了题目和样例，非常兴奋的写了个 0-1 背包上去，发现 WA 了，后来仔细想想不对，要求的是最大的安全系数 (暂且这么认为 - -)，这样定义的方程最有比较大的变化。

做如下定义：

定义 $dp[i]$ 为抢了 $i$ 元钱的最大安全系数，注意初始化的时候 $dp[0] = 1$，其他的设置成没有访问过，这里为了好转移，我将除了 $dp[0]$ 之外的 $dp$ 元素置为 $-1$ 。转移很好想，就是如下这个方程：

for (int i = 0; i < n; i++) {
  for (int j = max_money; j >= w[i]; j--) {
    if (dp[j - w[i]] != -1) { dp[j]=max(dp[j],dp[j-w[i]]*p[i];
    }
  }
}

注意 $p_i$ 表示的安全系数，这样数据中输入的并不是，所以要记得转化

这样用 O (n^2) 的时间复杂度就可以搞定这道 dp 题。

我的完整代码：

#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>

using namespace std;

const int MAX = 11000;
double dp[MAX];
int vol;

struct Node {
  int w;
  double p;
} node[120];

int main() {
  int t, n;
  double p;
  scanf("%d", &t);
  while (t--) {
    scanf("%lf%d", &p, &n);
    p = 1 - p;
    vol = 0;
    for (int i = 0; i < n; i++) {
      scanf("%d%lf", &node[i].w, &node[i].p);
      vol += node[i].w;
      node[i].p = 1 - node[i].p;
    }
    for (int i = 0; i <= vol; i++) {
      dp[i] = -1;
    }
    dp[0] = 1;
    for (int i = 0; i < n; i++) {
      for (int j = vol; j >= node[i].w; j--) {
        if (dp[j - node[i].w] != -1 && dp[j] < dp[j - node[i].w] * node[i].p) {
          dp[j] = dp[j - node[i].w] * node[i].p;
        }
      }
    }
    for (int i = vol; i >= 0; i--) {
      if (dp[i] >= p) {
        vol = i;
        break;
      }
    }
    printf("%d\n", vol);
  }
  return 0;
}