企业官网建设流程全解析

Part 1:题意：总共有 n 张 A 票，n 张 B 票。前面的人不断抛硬币选 A/B，只要对应票还有剩就拿走。求最后剩下两张是同一种票的概率（注意：输入给的是 2n，所以读入后要除以 2 得到 n）。

Part 2:为什么想到要用dp:我发现这一点很多题解都没讲，但这对于初学者十分重要，所以我在这里讲一下。原因1：要算剩下 i,j 张票的概率，依赖票数更多的状态。 比如算dp[3,2]要用到dp[4,2]和dp[3,3]。很多状态会被重复用到，暴力枚举所有抛硬币序列会爆炸，DP 存结果避免重复计算。原因2：不管前面抛硬币顺序是什么，只要当前剩余 A=i，B=j，后续概率完全一样。满足无后效性，这是 DP 最关键的判断点（这里的i,j代表什么意思之后会讲到）。

Part 3:dp:众所周知，做一道dp的题目大概要经历三步，分别为设置状态，定义初始值，状态转移，接下来，就分三步，一步一步讲。

1:设置状态：仔细读题，发现题目中只有三个值会改变，分别为已经卖出的A种票i张，已经卖出的B种票j张（这里的2<=i,j<=n）。所以，我们把状态设成dp[i][j]表示卖出i张A种票，j张B种票后两人拿到相同票的概率最好不过了。

2:设置初始值：（1）：一开始，当没有A种票（i==0），则只能拿到B种票，相同概率为1，则dp[0][j]=1(2<=j<=n).

(2):一开始，当没有B种票时（j==0），则只能拿到A种票，相同概率为1，则dp[i][j]=1(2<=i<=n)。就不难写出初始化代码

for(int i=2;i<=n/2;i++)//n/2注意！！！ { dp[0][i]=1; dp[i][0]=1; }

3：状态转移：假设我们现在在dp[i][j]，即买出了i张A票，j张B票，要得到dp[i][j]，上一步要么是刚卖掉一张 A（状态dp[i-1][j]），要么刚卖掉一张 B（状态dp[i][j-1]），如果此时 A、B 票都还有剩余，抛硬币各 0.5 概率。

for(int i=1;i<=n/2;i++) { for(int j=1;j<=n/2;j++) { dp[i][j]=dp[i-1][j]*0.5+dp[i][j-1]*0.5;//两张A或两张B都算相同 } }

Part 4:输出：最后的答案就在dp[n][n]里。

#include <bits/stdc++.h> using namespace std; double dp[1250][1250]; int main() { int n;//输入的是2N!!!! cin>>n; for(int i=2;i<=n/2;i++) { dp[0][i]=1; dp[i][0]=1; } for(int i=1;i<=n/2;i++) { for(int j=1;j<=n/2;j++) { dp[i][j]=dp[i-1][j]*0.5+dp[i][j-1]*0.5; } } printf("%.4lf",dp[n/2][n/2]); return 0; }

完美撒花qwq