UVA 10529 - Dumb Bones

题目链接

题意：你试图把一些多米诺骨牌排成直线，然后推倒它们。但是如果你在放骨牌的时候不小心把刚放的骨牌碰倒了，它就会把相临的一串骨牌全都碰倒，而你的工作也被部分的破坏了。 比如你已经把骨牌摆成了DD__DxDDD_D的形状，而想要在x这个位置再放一块骨牌。它可能会把左边的一块骨牌或右边的三块骨牌碰倒，而你将不得不重新摆放这些骨牌。 这种失误是无法避免的，但是你可以应用一种特殊的放骨牌方法来使骨牌更多的向一个方向倒下。 给出你要摆放的骨牌数目，以及放骨牌时它向左和向右倒的概率，计算你为完成任务摆放的骨牌数目的平均数。假设你使用了最佳的摆放策略。 输入将包含至多100个测试点，每个测试点占一行，包含需要摆放的骨牌数目n (1≤n≤1000)，以及两个非负实数Pl, Pr，表示骨牌向左和向右倒的概率。保证1＜Pl+Pr≤0.5。 最后一个测试点包含一个数0。对于每个测试点输出题目要求的数目，保留两位小数。

思路：概率，+区间dp，dp[i]表示有i个连续的多米诺骨牌，那么每次要组成i，就可以选中间任意一个位置，把这个骨牌分成两部分，dp[l]和dp[r]然后考虑在放一个，如果碰到左边，就要重新放左边，右边同理，根据期望公式，平均1 / (1 - pl - pr)步能成功放一个，也就是说之前都会有碰倒，那么碰倒的话需要走的步数期望为(1 + dp[l]pl + dp[r] pr)，所以期望为(1 + dp[l] pl + dp[r] pr) / (1 - pl - pr) + dp[l] + dp[r]，状态转移方程为
dp[i] = min(计算概率(dp[l], dp[r])) {枚举中间位置求出l, r}

于是这题递推求解就能过了，不过复杂度是O(n^2)，其实还有可以优化的地方

可以根据动态规划时候，dp[i]这个数组在找寻最小值的时候，其实方程是满足一个下凹函数的，所以这步实际上可以利用三分求解，复杂度为O(nlog(n))，然后实际上，对于下凹函数，那么其实对于下次找最小值的位置，是不会减小的，因此如果每次维护记录下上次找到答案的位置，这样均摊下来，时间复杂度就能优化到O(n)

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

#define INF 0x3f3f3f3f
const int N = 1005;
int n;
double p, pl, pr, dp[N];

double solve() {
    p = 1 - pl - pr;
    dp[0] = 0; dp[1] = 1 / p;
    int pre = 0;
    for (int i = 2; i <= n; i++) {
	dp[i] = INF;
	for (int j = pre; j < i; j++) {
	    int l = j, r = i - 1 - j;
	    double tmp = dp[l] + dp[r] + (pl * dp[l] + pr * dp[r] + 1) / p;
	    if (dp[i] > tmp) {
		dp[i] = tmp;
		pre = j;
	    }
	}
    }
    return dp[n];
}

int main() {
    while (~scanf("%d", &n) && n) {
	scanf("%lf%lf", &pl, &pr);
	printf("%.2lf\n", solve());	
    }
    return 0;
}