守卫者的挑战(据说在bzoj有但我没找到)

芒果君：一看就是概率dp（可是我不会啊，就算再裸也不会啊）。然后先从最后想，能够满足题意的状态是挑战次数>=L，获得价值>=0，那一定有f[总挑战数i][挑战成功数j][价值k]。转移很好写，无非两种情况，成功和不成功。不成功，i+1，其他不变，值*（1-p[i]）；成功，i+1，j+1，k+w，值是 ∑各种情况*p[i]。题目中有个关键信息是n<=200，也就是说极限情况是200* ±1，我们只需要开200*2的数组，将负数移个位。空间炸了怎么办，滚一滚啊。

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 double ans,p[],f[][][];

 int n,t,m,w;

 int main()

 {

     scanf("%d%d%d",&n,&t,&m);

     m=min(m,n);

     for(int i=;i<=n;++i) scanf("%lf",&p[i]),p[i]/=100.0;

     f[][][n+m]=;

     for(int i=;i<=n;++i){

         scanf("%d",&w);

         for(int j=;j<=n;++j) for(int k=;k<=(n<<);++k) f[i&][j][k]=f[i&^][j][k]*(-p[i]);

         for(int j=;j<n;++j) for(int k=;k<=(n<<);++k) f[i&][j+][min(k+w,n<<)]+=f[i&^][j][k]*p[i];

     }

     for(int i=t;i<=n;++i) for(int j=n;j<=(n<<);++j) ans+=f[n&][i][j];

     printf("%.6lf\n",ans);

     return ;

 }

巴特西

守卫者的挑战(据说在bzoj有但我没找到)

最新文章

热门文章