二分概率+矩乘+dp

也是二分概率,然后dp[i][j][k]表示当前到了i,有j条命,下一次的收益是k,然后矩乘转移,但是我自己的似乎wa了,抄了liu_runda的才行,具体不知道为什么

注释的是我自己写的,谁能告诉我哪里错了?

#include<bits/stdc++.h>
using namespace std;
const int N = ;
int n, r, q, tot;
int id[N][N];
double S;
struct matrix {
double a[N][N];
matrix() { for(int i = ; i <= tot; ++i) for(int j = ; j <= tot; ++j) a[i][j] = 0.0; }
matrix friend operator * (const matrix &a, const matrix &b) {
matrix ret;
for(int k = ; k <= tot; ++k)
for(int i = ; i <= tot; ++i) if(a.a[i][k] >= 1e-)
for(int j = ; j <= tot; ++j)
ret.a[i][j] += a.a[i][k] * b.a[k][j];
return ret;
}
void set() {
for(int i = ; i <= tot; ++i) a[i][i] = 1.0;
}
};
double calc(double p)
{
matrix A, B;
A.set();
/*
第i轮j条命这一次得k分
dp[i][j][k]=(dp[i+1][j + 1][k + 1] + k) * p
dp[i][j][k] += dp[i + 1][j - 1][1] * (1.0 - p)
矩阵乘法
*/
B.a[tot][tot] = 1.0;
for(int i = ; i <= q; ++i)
for(int j = ; j <= r; ++j)
{
if(i > ) B.a[id[i - ][]][id[i][j]] = 1.0 - p;
B.a[tot][id[i][j]] = p * (double)j;
if(i < q && j < r) B.a[id[i + ][j + ]][id[i][j]] = p;
else if(i < q) B.a[id[i + ][j]][id[i][j]] = p;
else if(j < r) B.a[id[i][j + ]][id[i][j]] = p;
else B.a[id[i][j]][id[i][j]] = p;
}
// for(int j = 0; j <= q; ++j)
// for(int k = 1; k <= r; ++k) B.a[tot][id[j][k]] = p * (double)k;
// for(int j = 0; j <= q; ++j)
// for(int k = 1; k <= r; ++k) B.a[id[min(j + 1, q)][min(k + 1, r)]][id[j][k]] = p;
// for(int j = 2; j <= q; ++j)
// for(int k = 1; k <= r; ++k) B.a[id[j - 1][1]][id[j][k]] = 1.0 - p;
for(int i = n; i; i >>= , B = B * B) if(i & ) A = A * B;
// double ret = 0.0;
// for(int i = 0; i <= tot; ++i)
// {
// for(int j = 0; j <= tot; ++j) printf("%.6f ", A.a[i][j]);
// puts("");
// }
// for(int i = 0; i < tot; ++i) ret += A.a[tot][i];
// printf("p = %.6f ret = %.6f\n", p, ret);
return A.a[tot][id[q][]];
}
int main()
{
scanf("%d%d%d%lf", &n, &r, &q, &S);
for(int i = ; i <= q; ++i)
for(int j = ; j <= r; ++j) id[i][j] = tot++;
// printf("tot = %d\n", tot);
double l = 0.0, r = 1.0, ans = -1.0;
while(r - l > 1e-)
{
double mid = (l + r) / 2.0;
if(calc(mid) > S) r = ans = mid;
else l = mid;
}
if(ans == -1.0) puts("Impossible.");
else printf("%.6f\n", ans);
return ;
}

最新文章

  1. C++中extern关键字用法小结
  2. dig的用法
  3. Erlang数据类型的表示和实现(4)——boxed 对象
  4. graph-tool文档(一)- 快速开始使用Graph-tool - 2.属性映射、图的IO和Price网络
  5. 【HDOJ】3696 Farm Game
  6. [置顶] cocos2d-x 植物大战僵尸(4) 帽子僵尸的产生
  7. 用Python写的简单脚本更新本地hosts
  8. web后端server优化
  9. IOS小技巧——使用FMDB时如何把一个对像中的NSArray数组属性存到表中
  10. 关于中值滤波算法,以及C语言实现(转)
  11. MVVM指南(课程学习)
  12. jQuery选择器---层次选择器总结
  13. Oracle常用语句
  14. vscode 好用插件
  15. c/c++ 标准容器 vector的内存空间是如何自动增长的
  16. 【LeetCode-数组篇】 1 Two Sum
  17. OI考试需注意的
  18. mysql/mariadb基于ssl的主从复制
  19. 基于tensorflow实现mnist手写识别 (多层神经网络)
  20. Alpha,Beta,RC,RTM,EVAL,CTP,OEM,RTL,VOL

热门文章

  1. Java Enum枚举的用法(转)
  2. Spring拦截器从Request中获取Json格式的数据
  3. python的分布式队列神器 Celery
  4. BUPT复试专题—寻找i*j=m的个数(2016)
  5. webrtc初探
  6. 怎么下载google商店的扩展程序?
  7. iPhone 适配之路
  8. js团购倒计时函数代码
  9. js 日期 (10 + &#39;&#39;).length == 10 ? &#39;0&#39; + 10 : 10;
  10. 【转载】轻松搞懂WebService工作原理