codevs1060搞笑世界杯(概率dp)

关键词：

/*
f[i][j]表示第i人买票时买了j张A票的概率
*/
#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;
double f[3000][3000];

int main()
{
    int n,i,j;
    scanf("%d",&n);n/=2;
    f[0][0]=1;
    for (i=1;i<=2*n;++i)
      for (j=0;j<=n;++j)
      {
          if (j>i) continue;
          if (j==0) f[i][j]=f[i-1][j]*0.5;
          else
          {
              if (j<n) f[i][j]=(f[i-1][j]+f[i-1][j-1])*0.5;
              else f[i][j]=f[i-1][j]+f[i-1][j-1]*0.5;
          }
      }
    printf("%.4f
",f[n*2-2][n]*2);
}

[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个点)这么一个状态。转移方程当... 查看详情