http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4808
题意：一个吸血鬼初始攻击力为f。n条路，他每次等概率选择一条路。如果攻击力大于这条路的c[i]，则花费t[i]天逃出（$t[i]=\frac{1+\sqrt{5}}{2} \times c[i]^2$），否则花费1天的时间继续选择路。问逃出去的期望天数（1<=c[i], f<=10000）
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;
const int N=20005;
double f[N];
int n, c[N], t[N];
double E(int x) {
if(f[x]>0) return f[x];
double &now=f[x];
for(int i=0; i<n; ++i) {
if(x>c[i]) now+=t[i];
else now+=E(x+c[i])+1;
}
now/=n;
return now;
}
int main() {
int now;
while(~scanf("%d%d", &n, &now)) {
for(int i=0; i<n; ++i) scanf("%d", &c[i]), t[i]=(1.0+sqrt(5))/2*c[i]*c[i];
printf("%.3f\n", E(now));
memset(f, 0, sizeof f);
}
return 0;
}
简单题无脑dp= =
设$f[i]$表示攻击力为$i$时逃出去所需要的期望天数..随便搞一下就行了..