●51NOD 1705 七星剑

题链：

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1705
题解：

期望dp，期望的线性性质
(首先对于第k颗星，一定只会用同一种膜法石去炼化它。)
定义f[k]表示炼化成功第k颗星最小的期望花费。
正向枚举k，然后枚举当前用哪个膜法石i去炼化
当然要为两种情况：炼化成功与否
1.成功：期望的花费即为prob[k][i]*c[i]
2.失败：
首先也有一个c[i]的花费(虽然没有成功，但是还是用了这个膜法石)，
令j=k-lose[k][i]，用拿i膜法石成功炼化第k颗星的期望花费为_f;
然后我们回到之前的某个状态：成功炼化了j-1颗星，
也就是说，我们如果要炼化成功第k颗星，我们还需要重新成功炼化第j~k这些星。
设重新成功炼化那1mol的星，期望需要w的花费，
按照期望的线性性质可以得到：w=f[j]+f[j+1]+......+f[k-1]+_f
若统计前缀和的话，即w=_f+sumf[k-1]-sumf[j-1];
所以可以得到失败时期望花费的转移：
(1-prob[k][i])*(c[i]+_f+sumf[k-1]-sumf[j-1])

所以综上，拿i膜法石成功炼化第k颗星的期望花费为：
_f=prob[k][i]*c[i]+(1-prob[k][i])*(c[i]+_f+sumf[k-1]-sumf[j-1]);
上式通过移项后，可以求出_f的值。
然后对f[k]取min即可：f[k]=min(f[k],_f(每种膜法石都可以得到一个_f))。

dp结束后sumf[7]=f[1]+f[2]+...+f[7]即是答案。

（输出-1的情况直接在读入时特判掉就好）

代码：

#include<bits/stdc++.h>

#define MAXN 105

#define doubleINF 1e37

using namespace std;

const double eps=1e-10;

int c[MAXN],lose[10][MAXN];

double prob[10][MAXN],f[10],sumf[10];

int N;

int main(){

	ios::sync_with_stdio(0);

	cin>>N;

	for(int i=1;i<=N;i++) cin>>c[i];

	for(int k=1;k<=7;k++){

		bool fg=0;

		for(int i=1;i<=N;i++)

			cin>>prob[k][i],fg|=(prob[k][i]>eps);

		if(!fg) return printf("-1\n"),0;

	}

	for(int k=1;k<=7;k++)

		for(int i=1;i<=N;i++)

			cin>>lose[k][i],lose[k][i]=k-lose[k][i];

	for(int k=1;k<=7;k++){

		f[k]=doubleINF;

		for(int i=1;i<=N;i++){

			double P=prob[k][i]; int C=c[i],j=lose[k][i];

			double _f=P*C+(1-P)*(C+sumf[k-1]-sumf[j-1]);

			_f=_f/P;

			f[k]=min(f[k],_f);

		}

		sumf[k]=sumf[k-1]+f[k];

	}

	cout<<fixed<<setprecision(10)<<sumf[7]<<endl;

	return 0;

}