其实和CF498bName that Tune差不多
题意:
现在需要依次输入n个字符,第i个字符输入的时候有pi的概率输错,不论是第几次输入(0<=pi<=0.5).每输入一个字符的用时为1.任意时刻都可以花费t的时间检查之前输入的字符有无错误(不论检查多少个字符,t的数值都是一样的),如果有错误就需要一次一次删除字符直到所有错误字符都被删除(只能从最后面往前删,如果第i个位置出错,那么第i个位置之后的所有字符无论对不对都必须被删除).如果采取最优策略,问将全部字符正确输入的期望时间.
分析:这里我们输入字符之后还必须通过检查确保输入的字符是正确的,那么在状态定义的时候就要体现这一点.如果定义f[i]为输入前i个字符并确保前i个字符正确的期望时间,将不容易转移.概率期望的题常常采用”逆序定义状态”,那么这道题中就定义f[i]为已经输入前n-i个字符并确保前n-i个字符正确时,再输入剩下的i个字符并确保它们正确所需的最优策略下期望时间.注意这里定义的是”最后i个字符的期望用时”而不是”前i个字符的期望用时”.显然,如果当前已经确保前n-i个字符正确,之后前n-i个字符就不会再发生变化了,如果后面的字符出错我们不需要删除已经确定正确的字符.
接下来考虑如何转移.我们进行的操作序列一定是:打几个字符,检查一次并进行必要的删除,打几个字符,检查一次并进行必要的删除,打几个字符检查一次并进行必要的删除.那么我们可以进行的决策就是下一次检查之前打多少个字符:是打1个字符再检查一次,还是打2个字符再检查一次.于是我们想到枚举下一次检查之前打的字符个数x.影响我们下一步行动的只有第一个错误出现的位置,那么当下一步打x个字符时(x<=i), f[i]=p(第一个错误出现在第1个字符)*(x+t+x+f[i])+p(第一个错误出现在第2个字符)*(x+t+x-1+f[i-1])+…+p(第一个错误出现在第x个字符)*(x+t+1+f[i-x+1])+p(不出现错误)*(x+t+f[i-x])
将式子右边的f[i]移项,就可以DP了.
注意即使不出现错误,我们也是在花费t的时间检查之后才能确保没有出现错误.
边界显然是f[0]=0
枚举f[i]对应的所有x值时,可以处理一下”第一个错误出现在第j个字符的概率”,注意一个细节:”打j个字符且没有出错”和”打j+1个字符且第一个错误出现在第j+1个字符”的概率是不同的.那么我们得到了一个O(n^3)的DP,但这样是不能通过的,需要优化.
仔细观察刚才得到的式子:
f[i]=p(第一个错误出现在第1个字符)*(x+t+x+f[i])+p(第一个错误出现在第2个字符)*(x+t+x-1+f[i-1])+…+p(第一个错误出现在第x个字符)*(x+t+1+f[i-x+1])+p(不出现错误)*(x+t+f[i-x])
我们发现,p(第一个错误出现在第1个字符)对于x=1,2,3…是相同的,p(第一个错误出现在第2个字符)对于x=2,3…是相同的,这暗示我们O(n^3)的做法中有大量可以省去的重复计算.
如果打x+1个字符再进行检查,则
f[i]=p(第一个错误出现在第1个字符)*(x+1+t+x+1+f[i])+p(第一个错误出现在第2个字符)*(x+1+t+x+f[i-1])+…+p(第一个错误出现在第x个字符)*(x+1+t+2+f[i-x+1])+p(第一个错误出现在第x+1个字符)*(x+1+t+1+f[i-x])+p(不出现错误)*(x+t+f[i-x-1])
//这式子鬼知道打没打错…
然后我们发现打x字符和打x+1个字符之间的变化是可以O(1)算出来的,那么我们就可以对每个i选择最优的x,O(n^2)从f[0]推到f[n]了…
#include<cstdio> #include<algorithm> using namespace std; const int maxn=3005; double f[maxn],p[maxn],P[maxn]; int main(){ freopen("sb_xiaoming.in","r",stdin); freopen("sb_xiaoming.out","w",stdout); int n,t;scanf("%d%d",&n,&t); for(int i=1;i<=n;++i)scanf("%lf",p+i); f[0]=0; for(int i=1;i<=n;++i){ P[0]=1;f[i]=1e30; for(int j=1;j<=i;++j)P[j]=P[j-1]*(1-p[n-i+j]); double tmp1=P[1]*f[i-1],tmp2=1-P[1]; for(int j=1;j<=i;++j){ f[i]=min(f[i],(tmp1+j+t+tmp2)/P[1]); tmp1+=P[j+1]*f[i-j-1];tmp1-=P[j+1]*f[i-j];tmp2+=1-P[j+1]; } } printf("%.6f ",f[n]); fclose(stdin);fclose(stdout); return 0; }