Title Link: Beating the Dataset - LightOJ 1274 - Virtual Judge (ppsucxtt.cn)

Simplified version of the question meaning: someone is asking a question, and the answer to the question is only yes and no. There are n questions in total. At the beginning, you know the number of questions in which the answer is yes. After each question you ask, the system will tell you what the correct answer is. The strategies you follow are as follows:

(1) The first question must be yes

(2) From the second question, the answer you get every time is the answer of the previous question. For example, i have done question i now, and the result of question i-1 is no, so i can get no directly on question i

Ask your expectation of the number of wrong questions.

Topic analysis: i've worked on this topic for a long time. Every time i read the topic, i get some new information (+ +). The first information i need to know is that the answers are randomly distributed. The next answer depends on the number of yes and no left. The second implicit condition to be mined is that, for example, a total of cntyes topics are yes, You happen to encounter the last yes in question i. according to the thinking of normal people, you should know that the answers to the following questions are No. however, since the answer to question i is yes, you will still get yes in question i+1 and be convinced~

We can use dynamic programming to solve this problem. Let f[i][j][k] mean that you have achieved the i-th problem. Among the i-th and previous problems, the correct answer of j-th problem is yes, and the correct answer of i-th problem is yes/no(k=1/0). Using this meaning, we can carry out recursive analysis. The recursive analysis is as follows:

Let the answer of n questions be yes. There are cntyes questions in total

When j + 1 < = cntyes: (it means that the later answer may be yes)

f[i][j][0] means that the i-th answer is no, then I will get no next time, and the probability of the next answer is yes is (cntyes-j) / (n-i), that is, this is the probability of my next mistake, and the probability of my next mistake is 1-mistake probability

f[i][j][1] means that if the answer is yes for the ith time, I will get yes next time. The probability of the answer is (cntyes-j) / (n-i), that is to say, this is the probability of my next false right, and the probability of my next false right is 1-false right

When j==cntyes: (it means that the following answers are all no)

f[i][j][0] means that the i-th answer is no, because the subsequent answers are all no, then I must be right next time, then f[i][j][0]=f[i+1][j][0]

f[i][j][1] means that the answer is yes for the ith time, because the subsequent answers are all no, then I will be wrong next time, and f[i][j][1]=f[i+1][j][0]+1

The probability that the first answer is yes is cntyes/n, which is the probability that I get it right for the first time. Then the probability that I get it wrong is 1-cntyes/n, and the answer is f[1][1][1]*cntyes/n+(f[1][0][0]+1)*cntno/n

Finally, it should be noted that due to space reasons, it is necessary to turn on the scrolling array

Here is the code:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
using namespace std;
const int N=5e3+10;
double f[2][N][2];//Indicates the expected number of errors after this state  
//f[i][j][k] the first dimension indicates the current processing to the ith answer
//The second dimension indicates that j YES has appeared in the i position and the answers to the previous questions
//The third dimension represents the case where the i-th answer is YES/NO(1/0)
int main()
{
	int T,n,m;
	cin>>T;
	for(int o=1;o<=T;o++)
	{
		scanf("%d%d",&n,&m);
		int cntyes=m-2*n;
		int cntno=n-cntyes;
		f[n&1][cntyes][0]=f[n&1][cntyes][1]=0;//Termination state 
		for(int i=n-1;i>=1;i--)
		{
			int minyes=max(0,i-cntno);
			int maxyes=min(i,cntyes);
			for(int j=minyes;j<=maxyes;j++)
			{
				double pyes=1.0*(cntyes-j)/(n-i);//Probability that the next answer is yes 
				double pno=1-pyes;//The probability that the next answer is no 
				if(j+1<=cntyes)//The answer after the i-th time may also appear yes 
				{
					f[i&1][j][0]=pyes*(f[(i+1)&1][j+1][1]+1)+pno*f[(i+1)&1][j][0];//If the answer to the i-th position is no, the next time you guess no, you have the probability of pyes guessing wrong 
					f[i&1][j][1]=pyes*f[(i+1)&1][j+1][1]+pno*(f[(i+1)&1][j][0]+1);//If the answer to the ith position is yes, the next time you guess yes, there is a (1-pyes) probability of wrong guess 
				}
				else//The answer after the i-th time can only be no 
				{
					f[i&1][j][0]=f[(i+1)&1][j][0];//If the answer to the i-th position is no, the next time you guess no, you must be right 
					f[i&1][j][1]=f[(i+1)&1][j][0]+1;//If the answer to the ith position is yes, the next time you guess yes, you must guess wrong and expect + 1 
				}
			}
		}
		double ans=f[1][1][1]*cntyes/n+(f[1][0][0]+1)*cntno/n;//The probability that the first answer is yes is cntyes/n, that is, the probability that the first guess is right is cntyes/n
		printf("Case %d: %.10lf\n",o,ans);
	}
	return 0;
}