题目大意
某人在打字机上打一个字符串，给出了他打每个字符出错的概率 q[i]。 打一个字符需要单位1的时间，删除一个字符也需要单位1的时间。在任意时刻，他可以花 t 的时间检查整个打出来的字符串，并且从当前光标删除到第一个出错的位置（留下的字符串要么为空，要么每个字符都是对的）。问你，他正确的打完该字符串最少需要花费的时间的期望值是多少
字符串的长度小于等于3000
题意有点绕，具体可以看看原题是怎么描述的
做法分析
首先确定这是一个概率DP的问题。
定义状态 f[i] 表示正确的打完前 i 个字符以后，最少还需要多少时间正确的打完所有字符
可以这样转移：往后连续打 j 个字符之后再来花时间检查字符串，并且删除，具体的转移方程就是这样的：
对于一个具体的 j ：
令 g[i][j]= j+t
+q[i+1]*(f[i]+j) // 在第 i+1 位出错
+p[i+1]*q[i+2]*(f[i+1]+j-1) // 在第 i+2 位出错
+p[i+1]*p[i+2]*q[i+3]*(f[i+2]+j-2) // 在第 i+3 位出错
+......
+p[i+1]*p[i+2]*p[i+3]*...*q[i+j]*(f[i+j-1]+1) // 在第 i+j 位出错
+p[i+1]*p[i+2]*p[i+3]*...*p[i+j]*f[i+j] // 连续打的 k 个字符全部正确
上式中，p[i] 表示第 i 个字符正确的概率，q[i] 表示第 i 个字符错误的概率，p[i]+q[i]=1
考虑到上式需要移项来解出 f[i] 的具体表达式，而移到等式右边的始终是 q[i+1]*f[i]，不妨对 g[i][j] 稍作修改
令 g[i][j]= j+t
+q[i+1]*j // 在第 i+1 位出错
+p[i+1]*q[i+2]*(f[i+1]+j-1) // 在第 i+2 位出错
+p[i+1]*p[i+2]*q[i+3]*(f[i+2]+j-2) // 在第 i+3 位出错
+......
+p[i+1]*p[i+2]*p[i+3]*...*q[i+j]*(f[i+j-1]+1) // 在第 i+j 位出错
+p[i+1]*p[i+2]*p[i+3]*...*p[i+j]*f[i+j] // 连续打的 k 个字符全部正确
那么，我们就有：f[i]=min{ g[i][j] }/(1-q[i+1])=min{ g[i][j] }/p[i+1]，1≤j≤n-i
初始状态：f[n]=0
目标状态：f[0]
虽然状态转移方程推出来了，但是不要急，注意数据范围：n≤3000
按照上面的式子 DP 的话，这个做法是 n3 的复杂度，还需要做一些优化
我们观察 g[i][j] 和 g[i][j+1] 的关系：
g[i][1]=1+t+q[i+1]+p[i+1]*f[i+1]
g[i][2]=2+t+q[i+1]*2+p[i+1]*q[i+2]*(f[i+1]+1)+p[i+1]*p[i+2]*f[i+2]
=g[i][1]+1+q[i+1]+p[i+1]*p[i+2]*f[i+2]+(p[i+1]*q[i+2]-p[i+1])*f[i+1]+p[i+1]*q[i+2]
=g[i][1]+1+q[i+1]+p[i+1]*q[i+2]+p[i+1]*p[i+2]*f[i+2]-p[i+1]*p[i+2]*f[i+1]
=g[i][1]+1+1-p[i+1]*p[i+2]+p[i+1]*p[i+2]*f[i+2]-p[i+1]*p[i+2]*f[i+1]
=g[i][1]+2+p[i+1]*p[i+2]*(f[i+2]-f[i+1]-1)
同理：g[i][3]=g[i][2]+2+p[i+1]*p[i+2]*p[i+3]*(f[i+3]-f[i+2]-1)
推到这里，规律已经呼之欲出了。运用这个规律，便可以省去一个循环，把 n3 变成 n2
写的那么复杂，其实代码就几行...
非常好的一道题目，赞一个！
参考代码
#include <iostream>
#include <cstring>
#include <cstdio> using namespace std; const int N=; int n, t;
double p[N], f[N]; int main()
{
while(scanf("%d%d", &n, &t)!=EOF)
{
for(int i=; i<=n; i++) scanf("%lf", &p[i]), p[i]=-p[i];
f[n]=;
for(int i=n-; i>=; i--)
{
double cur=t++(-p[i+])+p[i+]*f[i+];
double temp=p[i+];
f[i]=cur;
for(int j=; i+j<=n; j++)
{
temp*=p[i+j];
cur+=-temp+temp*f[i+j]-temp*f[i+j-];
f[i]=min(f[i], cur);
}
f[i]/=p[i+];
}
printf("%.8lf\n", f[]);
}
return ;
}
SGU 422