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 = 1000005;
int n;
double p, pl, pr, dp[N];

double cal(int l, int r) {
    return dp[l] + dp[r] + (pl * dp[l] + pr * dp[r] + 1) / p;
}

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] = cal(pre, i - pre - 1);
	for (int j = pre + 1; j < i; j++) {
	    int l = j, r = i - 1 - j;
	    double tmp = cal(l, r);
	    if (dp[i] >= tmp) {
		dp[i] = tmp;
		pre = j;
	    }
	    else break;
	}
    }
    return dp[n];
}

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