[关闭]
@ysner 2018-08-05T12:24:42.000000Z 字数 1388 阅读 1963

守卫者的挑战

DP


题面

初始值为,现经过一段数,有的概率加上第个数。问最后值且加了个数的概率。

解析

注意到都是没有意义的,于是可以把的范围视为
直接设表示处理了第个数,加了个数,值为的概率。
决策就是是否加上这个数。

为了防止第三维变负,,空间要开到
注意到因为字节,下该数组会导致
滚掉第一维即可。

复杂度同阶)。

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstdlib>
  4. #include<cstring>
  5. #include<cmath>
  6. #include<algorithm>
  7. #include<vector>
  8. #define re register
  9. #define il inline
  10. #define ll long long
  11. #define max(a,b) ((a)>(b)?(a):(b))
  12. #define min(a,b) ((a)<(b)?(a):(b))
  13. #define fp(i,a,b) for(re int i=a;i<=b;i++)
  14. #define fq(i,a,b) for(re int i=a;i>=b;i--)
  15. using namespace std;
  16. const int mod=1e9+7,N=1e6+100;
  17. int n,l,k,sum;
  18. long double dp[2][205][410],ans;
  19. struct cha{int w;long double p;}a[N];
  20. il ll gi()
  21. {
  22. re ll x=0,t=1;
  23. re char ch=getchar();
  24. while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  25. if(ch=='-') t=-1,ch=getchar();
  26. while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  27. return x*t;
  28. }
  29. il int del(re int x)
  30. {
  31. if(x>400) return 400;
  32. }
  33. int main()
  34. {
  35. freopen("guard.in","r",stdin);
  36. freopen("guard.out","w",stdout);
  37. n=gi();l=gi();k=gi();k=min(k+200,400);
  38. fp(i,1,n) scanf("%Lf",&a[i].p);fp(i,1,n) a[i].w=gi();
  39. re int now=1,nxt=0;
  40. fp(i,200,400) fp(j,l,n) dp[now][j][i]=1;
  41. fq(i,n,1)
  42. {
  43. swap(now,nxt);
  44. memset(dp[now],0,sizeof(dp[now]));
  45. fp(j,0,i)
  46. fp(v,0,400)
  47. {
  48. dp[now][j][v]+=a[i].p*dp[nxt][j+1][del(v+a[i].w)]/100;
  49. dp[now][j][v]+=(100-a[i].p)*dp[nxt][j][v]/100;
  50. }
  51. }
  52. printf("%.6Lf\n",dp[now][0][k]);
  53. fclose(stdin);
  54. fclose(stdout);
  55. return 0;
  56. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注