题目
题解
用 f [ i ] f[i] f[i]表示 i i i颗星的最小期望
从第 i − 1 i-1 i−1个点转移到i，若成功概率为 p p p，失败后退 l l l格，那么
p ⋅ f [ i ] + ( 1 − p ) ⋅ f [ i − i − l ] = f [ i − 1 ] + c [ j ] p\cdot f[i]+(1-p)\cdot f[i-i-l]=f[i-1]+c[j] p⋅f[i]+(1−p)⋅f[i−i−l]=f[i−1]+c[j]

#include<bits/stdc++.h>
using namespace std;
double c[102],f[8],p[8][102];
int l[8][102],fl,i,j,n;
int main(){
	scanf("%d",&n);
	for (i=1;i<=n;i++) scanf("%lf",&c[i]);
	for (i=1;i<=7;i++){
		fl=0;
		for (j=1;j<=n;j++) scanf("%lf",&p[i][j]),fl|=p[i][j]>1e-6;
		if (!fl){
			puts("-1");
			return 0;
		}
	}
	for (i=1;i<=7;i++)
		for (j=1;j<=n;j++) scanf("%d",&l[i][j]);
	for (i=1;i<=7;i++) f[i]=1e99;
	for (i=1;i<=7;i++)
		for (j=1;j<=n;j++)
			if (p[i][j]>1e-6) f[i]=min(f[i],(f[i-1]+c[j]-(1-p[i][j])*f[i-1-l[i][j]])/p[i][j]);
	printf("%.9lf",f[7]);
}