HDU 5781 ATM Mechine
题目大意：某个未知整数x等概率的分布在[0,k]中。每次你都可以从这个整数中减去一个任意整数y，如果x>=y，那么x=x-y，操作次数累计加1；否则，将会受到一次错误提示。当错误提示超过w次，将会对你的人生产生影响。现在，你的任务是将x逐步变为0，求最少操作次数的期望值。
题目分析：概率DP求期望。定义状态dp(k,w)表示整数分布在[0,k]，错误提示次数上限为w时的最少操作次数的期望。
则dp(k,w)=min(p1*dp(k-y,w)+p2*(y-1,w-1))+1，其中p1、p2分别为k>=y、k<y的概率，p1=(k-y+1)/(k+1)、p2=y/(k+1)。因为你非常聪明，所以你每次都会二分的选择要减掉的整数y。根据题目的数据规模，你最多会操作log2(k)+1次，所以你被错误提示的次数最多log2(k)次。这样，便大大减少了状态数目，使得上述方程能够得以实现。
输入：
1 1
4 2
20 3
输出：
1.000000
2.400000
4.523810
参考代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define maxn 2010
#define LL long long
double dp[maxn][maxn];
#define inf 0x3f3f3f3f
double getdp(int i,int j)
{
if(i==0)
return dp[i][0]=0;
if(j==0)
return dp[i][j]=inf;
if(dp[i][j]!=-1.0)
return dp[i][j];
double ans=inf;
for(int k=1;k<=i;k++)
{
ans=min(ans,(i+1-k)/(i+1.0)*getdp(i-k,j)+k/(i+1.0)*getdp(k-1,j-1)+1);
}
return dp[i][j]=ans;
}
int main()
{
int k,w;
for(int i=0;i<maxn;i++)
for(int j=0;j<maxn;j++)
dp[i][j]=-1.0;
while(~scanf("%d%d",&k,&w))
{
printf("%.6f\n",getdp(k,min(w,15)));
}
}
最新文章
- 怎样运用好ZBrush中的布尔运算
- linux下安装mysql手记
- chrome全局搜索
- 堆排序（C++版）
- java推断字符串是否为乱码
- MFC DialogBar 按钮灰色不响应
- HTTP请求方式中get和post的区别
- 简单概述 .NET Framework 各版本区别
- 设计模式之UML类图
- Unable to start EmbeddedWebApplicationContext due to missing EmbeddedServletContainerFactory bean.
- 修改系统启动项 grub2配置的方法 ubuntu[转]
- ENode 2.0
- JSON【介绍、语法、解析JSON】
- windows之电脑开机出现 this product is covered by one or more of the following prtents
- ES5-ES6-ES7_iterator和for of
- JS创建对象之工厂模式
- 理解DeepBox算法
- linux下升级gcc版本（gcc-7）
- 使用Python请求http/https时设置失败重试次数
- SQL记录-PLSQL-DBMS输出