本文共 1136 字，大约阅读时间需要 3 分钟。
期望，$dp$。
设$dp[i]$为当前战斗力为$i$的情况下，到达目标状态的期望值。倒着推一遍就可以了。
#pragma comment(linker, "/STACK:1024000000,1024000000")#include #include #include #include #include #include #include #include #include #include using namespace std;typedef long long LL;const double pi=acos(-1.0),eps=1e-10;void File(){ freopen("D:\\in.txt","r",stdin); freopen("D:\\out.txt","w",stdout);}template inline void read(T &x){ char c = getchar(); x = 0; while(!isdigit(c)) c = getchar(); while(isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); }}double dp[25000];int n,f,c[15000],mx;int t[25000];int main(){ while(~scanf("%d%d",&n,&f)) { for(int i=1;i<=n;i++) { scanf("%d",&c[i]); mx=max(mx,c[i]); t[i]=(int)((1.0+sqrt(5.0))/2.0*c[i]*c[i]); } memset(dp,0,sizeof dp); for(int i=mx+1;i<=21000;i++) for(int j=1;j<=n;j++) dp[i]+=1.0/n*t[j]; for(int i=mx;i>=f;i--) { for(int j=1;j<=n;j++) { if(i>c[j]) dp[i]=dp[i]+1.0/n*t[j]; else dp[i]=dp[i]+1.0/n*(dp[i+c[j]]+1); } } printf("%.3f\n",dp[f]); } return 0;}
转载于:https://www.cnblogs.com/zufezzt/p/6343621.html