hdu 6558 The Moon（dp+概率+记忆化)*

题目链接：hdu 6558

The Moon
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 539 Accepted Submission(s): 249
Special Judge

Problem Description
The Moon card shows a large, full moon in the night’s sky, positioned between two large towers. The Moon is a symbol of intuition, dreams, and the unconscious. The light of the moon is dim, compared to the sun, and only vaguely illuminates the path to higher consciousness which winds between the two towers.

Random Six is a FPS game made by VBI(Various Bug Institution). There is a gift named “Beta Pack”. Mr. K wants to get a beta pack. Here is the rule.
Step 0. Let initial chance rate q = 2%.
Step 1. Player plays a round of the game with winning rate p.
Step 2. If the player wins, then will go to Step 3 else go to Step 4.
Step 3. Player gets a beta pack with probability q. If he doesn’t get it, let q = min(100%, q + 2%) and he will go to Step 1.
Step 4. Let q = min(100%, q + 1.5%) and goto Step 1.
Mr. K has winning rate p% , he wants to know what’s the expected number of rounds before he needs to play.

Input
The first line contains testcase number T (T ≤ 100). For each testcase the first line contains an integer p (1 ≤ p ≤ 100).

Output
For each testcase print Case i : and then print the answer in one line, with absolute or relative error not exceeding 106.

Sample Input

2
50
100

Sample Output

Case 1: 12.9933758002
Case 2: 8.5431270393

分析：

没太看懂题目o(╯□╰)o
只要看懂题目，就比较好办了。先将小数化成整数，然后模拟一下，将公式推出来，然后记忆化，对于q==200的情况，只要将它代入到solve中的else部分就可得到一个等比数列，求个和就可得出为1/p

代码：

#include <bits/stdc++.h>

using namespace std;
#define eps 1e-4

double dp[105][210];

double solve(int q,int p)
{
	if(dp[p][q]) return dp[p][q];
	if(q==200)
	{
		return 1/(p/100.0);
	}
	else
	{
		
		
		return dp[p][q]=(p/100.0)*(q/200.0+(200-q)/200.0*(solve(min(q+4,200),p)+1))+(100-p)/100.0*(solve(min(q+3,200),p)+1);
		
		
	}
}

int main()
{
	int t, p;
	scanf("%d",&t);
	int o=0;
	while(t--)
	{
		scanf("%d",&p);
		memset(dp,0,sizeof(dp));
		printf("Case %d: %.10lf\n",++o,solve(4,p));
	}
	
	return 0;
}