关键词：

题目梗概

世界会售卖两种票，一种是A票，一种是B票。它们的数量都是n。

假设前面的人买A,B票的概率一定是1/2的情况下。

问如果队尾的两个人，买到同一种票的概率是多少。 

思考

接触的第一道概率相关的题目，不知道算不算dp。

首先两个人买到同一种票的情况有两种，一种是AA票 一种是BB票。

所以我们关注的重点应该是 A,B票的数量。

$dpleft [ i ight ]left [ j ight ] = left (dpleft [ i-1 ight ] left [ j ight ] + dpleft [ i ight ] left [ j-1 ight ]   ight ) imes frac{1}{2}$

从1,1到n,n 计算每次i张A票 j张B票的 概率

需要注意的是特殊处理的 $dpleft [ i ight ]left [ 0 ight ] left ( iin 1  mapsto   n   ight )$ 

$dpleft [ 0 ight ]left [ j ight ] left ( j in 1  mapsto   n   ight )$

#include <cstdio>
#include <iostream>
#include <algorithm>
double dp[1333][1333];
int n;

int main(){
    scanf("%d",&n);
    //n = A 票 + B票 
    dp[1][1]=0;
    for(int i=2;i<=n/2;i++)
            dp[i][0]=dp[0][i]=1;
    for(int i=1;i<=n/2;i++)
        for(int j=1;j<=n/2;j++)
            dp[i][j] = (dp[i-1][j]+dp[i][j-1])*0.5;
    printf("%.4f
",dp[n/2][n/2]);
    return 0;    
}

[codevs]1060搞笑世界杯

CODEVS上一道钻石题，还是DP的思想，先来题目1060搞笑世界杯时间限制:1s空间限制:128000KB题目等级:钻石Diamond题解题目描述Description随着世界杯小组赛的结束,法国,阿根廷等世界强队都纷纷被淘汰,让人心痛不已.于是有人组织了一场... 查看详情

概率期望dp

1.codevs1060搞笑世界杯题目描述 Description搞笑世界杯的球票出售方式也很特别,它们只准备了两种球票.A类票------免费球票B类票-------双倍价钱球票.购买时由工作人员通过掷硬币决定,投到正面的买A类票,反面的买B类票.并且主办... 查看详情

codevs1060搞笑世界杯

1060搞笑世界杯  时间限制:1s 空间限制:128000KB 题目等级:钻石Diamond题解 查看运行结果  题目描述 Description   随着世界杯小组赛的结束,法国,阿根廷等世界强队都纷纷被淘汰,让人心痛不已.于... 查看详情

codeves1060搞笑世界杯

1060搞笑世界杯 时间限制:1s空间限制:128000KB题目描述Description   随着世界杯小组赛的结束,法国,阿根廷等世界强队都纷纷被淘汰,让人心痛不已.于是有人组织了一场搞笑世界杯,将这些被淘汰的强队重新组织起来和世... 查看详情

●洛谷p1291[shoi2002]百事世界杯之旅

题链：https://www.luogu.org/recordnew/show/5861351题解：dp，期望 定义dp[i]表示还剩下i个盖子没收集时，期望还需要多少次才能手机完。 初始值：dp[0]=0 显然对于一个状态，我们随机得到一个盖子，有两种可能： 1.得到了曾经没有的盖子... 查看详情

bzoj_1060_时态同步_树形dp

BZOJ_1060_时态同步_树形DP题意：http://www.lydsy.com/JudgeOnline/problem.php?id=1060分析：水水的树形DP。用儿子的最大值更新父亲，边更新边累加ans。代码：#include<stdio.h>#include<string.h>#include<algorithm>usingnamespacestd; 查看详情

cf1060fshrinkingtree(代码片段)

...每个点成为最后编号的情况，并且把这个点rt作为根其实概率是：p/(n-1)!*(1/2)^k这里的p是所有缩边的排列中，和rt合并有k次的方案数。我们只计算p*(1/2)^k部分，最后统一除以(n-1)! 基础的想法：f[x][k]x为根的子树，和x合并k次的 查看详情

bzoj3566[shoi2014]概率充电器树形概率dp

...SHOI刚刚发布了引领世界潮流的下一代电子产品——概率充电器:“采用全新纳米级加工技术,实现元件与导线能否通电完全由真随机数决定!SHOI概率充电器,您生活不可或缺的必需品!能充上电吗?现在就试试看吧!”SHOI概... 查看详情

[bzoj1060][zjoi2007]时态同步树形dp

1060:[ZJOI2007]时态同步TimeLimit: 10Sec  MemoryLimit: 162MBSubmit: 2988  Solved: 1086[Submit][Status][Discuss]Description　　小Q在电子工艺实习课上学习焊接电路板。一块电路板由若干个元件组成，我们不妨称之为节 查看详情

codevs1068(dp)

题目链接:http://codevs.cn/problem/1068/ 题意:中文题诶~ 思路:dp用dp[i][j][k][l]表示取i个1,j个2,k个3,l个4时最大贡献为多少,那么初始化为dp[0][0][0][0]=v[1],其中v[i]表示i这点的权值.动态转移方程式为:1intdis=i+2*j+3*k+4*l+1;2if(i)dp[i][j][k][l]=m... 查看详情

codevs1169,51nod1084(多线程dp)

先说下codevs1169吧,题目链接:http://codevs.cn/problem/1169/ 题意:中文题诶~ 思路:多线程dp用dp[i][j][k][l]存储一个人在(i,j),一个人在(k,l)位置时对答案的最大贡献,那么动态转移方程式为:dp[i][j][k][l]=max(max(dp[i-1][j][k-1][l],dp[i-1][j][k][l-1])... 查看详情

codevs1031质数环(dp）

题目大意：http://codevs.cn/problem/1031/ #include<iostream>#include<cmath>#include<algorithm>#include<string>usingnamespacestd;intarr[17]={0};boolf[17]={false};boolisPrime(inta 查看详情

codevs1017乘积最大（dp）

题目大意：http://codevs.cn/problem/1017/ 题解：#include<iostream>usingnamespacestd;charch[45];intn,k;longlongintarr[45][7];longlongintdp[45][7];intmain(){cin>>n>>k>>ch;for(inti=0; 查看详情

codevs1014装箱问题（dp）

题目大意：http://codevs.cn/problem/1014/源码：#include<iostream>#include<cmath>#include<cstdio>#include<algorithm>#include<cstring>usingnamespacestd;intv,n;intarr[50];intmain(){c 查看详情

luogup1060开心的今明(dp背包)

P1060开心的金明题目描述金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就... 查看详情

bzoj1060时态同步[树形dp]

Description小Q在电子工艺实习课上学习焊接电路板。一块电路板由若干个元件组成，我们不妨称之为节点，并将其用数字1,2,3….进行标号。电路板的各个节点由若干不相交的导线相连接，且对于电路板的任何两个节点，都存在且仅... 查看详情

[codevs1050]棋盘染色2（状态压缩dp）

   题目大意：有一个5*N(≤100)的棋盘，棋盘中的一些格子已经被染成了黑色，求最少对多少格子染色，所有的黑色能连成一块。   这题卡了我1h，写了2.6k的代码，清明作业一坨还没做啊。。。之前一直以为... 查看详情

codevs2853方格游戏--棋盘dp(代码片段)

方格游戏：http://codevs.cn/problem/2853/ 这和传纸条和noip方格取数这两个题有一定的相似性，当第一眼看到的时候我们就会想到设计$dp[i][j][k][l]$(i,j表示一个人走到i行j个点，而另一个人走到k行第l个点)这么一个状态。转移方程当... 查看详情