LeetCode-Day49

HDU：2050 折线分割平面

问n条折线最多能将平面分成几个区域？

可以先考虑n条直线分割平面的最多个数，令其为$Z(n)$

对于折线，先算出$Z(2n)$的值，然后考虑一个V型线，如果这两条直线相交会有四个面，但是相交后不继续走会减少两个面。也就是说，一个尖点会减少两个面。以此类推，$n$个V型线最后的结果$ans(n) = Z(2n) - 2n$。而$Z(n) = Z(n - 1) + n$，因此$Z(n) = \frac{n(n+1)}{2} + 1$。所以$ans(n) = 2n^2-n+1$

n个平面最多把3维空间分成几部分？

https://www.zhihu.com/question/36889571/answer/339676165

HDU：2955 Robberies

背包问题

n件物品，盗窃第i件被抓获的概率为p[i],第i件价值为a[i]，问被抓获概率小于P的情况下可获得的最大价值。不同物品的盗窃事件概率相互独立。n范围100，a[i]范围100。

Dp

总价值范围10000，以f[j]表示获取价值和为j的物品时最小的被抓获概率。

Dp方程：f[j] = min(f[j], f[j-a[i]] + (1. - f[j-a[i]])* p[i])

#include <bits/stdc++.h>
using namespace std;
const double diff = 0.00001;
const int MAXN = 10005;
const int MAXW = 105;
double P;
int total;
double dp[MAXN];
double catchp[MAXW];
int value[MAXW];
int maxWeight = 0;

void solve() {
    for(int i = 1; i <= maxWeight; i++) {
        dp[i] = P * 2;
    }
    dp[0] = 0;
    for(int i = 1; i <= total; i++) {
        for(int j = maxWeight; j >= value[i]; j--) {
            dp[j] = min(dp[j], dp[j - value[i]] + (1.0 - dp[j - value[i]]) * catchp[i]);
        }
    }
    for(int i = maxWeight; i >= 0; i--) {
        if(dp[i] <= P) {
            printf("%d\n", i);
            return ;
        }
    }
}

int main() {
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        scanf("%lf%d", &P, &total);
        maxWeight = 0;
        for(int j = 1; j <= total; j++) {
            scanf("%d%lf", &value[j], &catchp[j]);
            maxWeight += value[j];
        }
        solve();
    }
}