Coins of luck 动态规划

Luck is the key to life. When I have to decide something, I will make my decision by flipping a coin. And then, I have two things to do. First, I have the decision made. Second, I go to the nearest church and donate the coin.

But there are always too many things I have to decide. For example, what should I eat today for lunch? OK, now we are talking about a decision, so let us assume that I have two kinds of food: quick-served noodle A and quick-served noodle B.

I just have bought N bowls of noodle A and N bowls of noodle B. If I have some space to make a decision (i.e. having two kinds of quick-served noodle to choose from), then I will flip a coin to decide which kind of noodle to eat.

My question is, before I eat up all 2 * N bowls of quick-served noodle, what is the mathematical expectation of the number of coins I will have to donate.

Input
Standard input will contain multiple test cases. The first line of the input is a single integer T (1 <= T <= 1000) which is the number of test cases. And it will be followed by T consecutive test cases.

Each test case contains an integer N (1 <= N <= 1000).

Output
Results should be directed to standard output. The output of each test case should be a single real number, which is the mathematical expectation of the number of coins I have to donate. The result should be accurate to two digits after the fractional point.

Sample Input
2
1
2

Sample Output
1.00
2.50

题目意思是说，一个人喜欢用抛硬币来解决一些事情，当有事情需要决定时就进行抛硬币，之后将用到的硬币捐出去，现在有两种各N碗面条，分别记为A和B，求吃完全部面条捐的硬币的期望值。

一开始以为是一个思维题，后来仔细想想应该用动态规划，先打表，之后输出对角线上的对应位置即可，细节在于求状态转移方程，首先不难得出，当只有一种面条时，不需要投硬币，所以A=0或者B=0时dp的值都是0，其余时候，假设有i个A面条和j个B面条，那么这个状态可以由i-1个A面条j个B面条或者i个A面条j-1个B面条转移过来，而增加的这一个在投硬币的时候需要再乘以1/2，次数需要再加一次，动态规划理解不清楚，这里理解的不透彻，在做题的时候算是投机了，因为题目给的测试用例有i和j都是1的情况，所以凑了个巧卡出来了转移方程
dp[i][j] = dp[i-1][j] * 0.5 + dp[i][j-1]*0.5 + 1

#include<iostream>
#include<stdio.h>
#include<memory.h>
#include<algorithm>
using namespace std;
double dp[1005][1005];
int main()
{
int t;
cin>>t;
memset(dp,0,sizeof(dp));
for(int i=1;i<=1004;i++)
for(int j=1;j<=1004;j++)
dp[i][j]=dp[i-1][j]*0.5+dp[i][j-1]*0.5+1;
for(int i=0;i<t;i++)
{
int temp;
cin>>temp;
printf("%.2lfn",dp[temp][temp]);
}
}

最后

以上就是迅速路灯为你收集整理的Coins of luck 动态规划的全部内容，希望文章能够帮你解决Coins of luck 动态规划所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。