博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
HDU5781 ATM Mechine(DP 期望)
阅读量:6967 次
发布时间:2019-06-27

本文共 1154 字,大约阅读时间需要 3 分钟。

应该是machine

 

和POJ3783 Balls类型相似。

现在上界为i元,猜错次数最多为j时,开始猜测为k元,有两种情况:

1 猜中:(i - k + 1) * dp[i - k][j]

2 猜不中 k * dp[k - 1][j - 1] 

两种情况的均值即为第一次猜测为k时的期望,1 <= k <= i + 1,枚举k,取最小值。

 

另外其实m取不到2000,由二分思想最多十几次(开始也没想到,一直不能把n^3的复杂度降下来)。

 

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;typedef long long LL;const int N = 2010, INF = 0x3F3F3F3F;#define MS(a, num) memset(a, num, sizeof(a))#define PB(A) push_back(A)#define FOR(i, n) for(int i = 0; i < n; i++)double dp[N][20];void solve(int n, int m){ for(int i = 0; i <= m; i++){ dp[0][i] = 0; } for(int i = 1 ; i <= n; i++){ dp[i][0] = INF; } for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ dp[i][j] = INF; for(int k = 1; k <= i + 1; k++){ dp[i][j] = min(dp[i][j], (k * dp[k - 1][j - 1] + (i - k + 1) * dp[i - k][j] ) / (i + 1) + 1); } } }}int main(){ solve(2008, 15); int k, w; while(~scanf("%d %d", &k, &w)){ w = min(w, 15); printf("%.6f\n", dp[k][w]); } return 0;}

  

转载于:https://www.cnblogs.com/IMGavin/p/5736256.html

你可能感兴趣的文章
memcache---mongodb---redis比较
查看>>
C#之Action和Func的用法
查看>>
css transform旋转属性
查看>>
Python DB-API 2.0规范
查看>>
BOM
查看>>
模板方法模式理解
查看>>
eclipse加SDK加海马模拟器实现Android项目开发的配置及一个简单的实现案例
查看>>
ASP.NET 弹出窗口
查看>>
Bzoj1001 [BeiJing2006]狼抓兔子
查看>>
9.27 h5日记
查看>>
二分例题2
查看>>
Javascript单线程实现
查看>>
火电电厂相关业务知识
查看>>
Magento 模版路径
查看>>
Taking water into exams could boost grades 考试带瓶水可以提高成绩?
查看>>
一对多和多对一的关系,用mybatis写
查看>>
七 递归与二分法、匿名函数、内置函数
查看>>
hdu 1001
查看>>
JavaScript速记
查看>>
两栏布局,三栏布局,等高布局,流式布局
查看>>