关键词：
设f[i][j]为掉到f[i][j]时的概率然后分情况随便转移一下就好
主要是要手写分数比较麻烦
#include<iostream>
#include<cstdio>
using namespace std;
const int N=55;
int n,m;
char a[N][N];
long long gcd(long long a,long long b)
return !b?a:gcd(b,a%b);
struct fs
long long x,y;
fs(long long X=0,long long Y=1)
x=X,y=Y;
fs operator + (const fs &a) const
long long d=gcd(a.y,y),l=a.y/d*y;
fs b=fs(l/y*x+l/a.y*a.x,l);
long long g=gcd(b.x,b.y);
return fs(b.x/g,b.y/g);
fs operator * (const fs &a) const
fs b=fs(x*a.x,y*a.y);
long long g=gcd(b.x,b.y);
return fs(b.x/g,b.y/g);
f[N][N];
int main()
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
a[i][j]=getchar();
while(a[i][j]!=‘*‘&&a[i][j]!=‘.‘)
a[i][j]=getchar();
f[1][1]=fs(1,1);
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
if(a[i][j]==‘*‘)
f[i+1][j]=f[i+1][j]+f[i][j]*fs(1,2);
f[i+1][j+1]=f[i+1][j+1]+f[i][j]*fs(1,2);
else
f[i+2][j+1]=f[i+2][j+1]+f[i][j];
printf("%lld/%lld
",f[n+1][m+1].x,f[n+1][m+1].y);
return 0;
/*
5 2
*
*.
***
*.**
*****
*/bzoj1867:[noi1999]钉子和小球dp(代码片段)
设f[i][j]为掉到f[i][j]时的概率然后分情况随便转移一下就好主要是要手写分数比较麻烦#include<iostream>#include<cstdio>usingnamespacestd;constintN=55;intn,m;chara[N][N];longlonggcd(longlonga,longlongb)return!b?a:gcd(b,a%b);s 查看详情
[bzoj1867][noi1999][钉子和小球](动态规划)
...50）和m（0<=m<=n）。以下n行依次为木板上从上至下n行钉子的信息，每行中‘*’表示钉子还在，‘.’表示钉子被拔去，注意在这n行中空格符可能出现在任何位置。Output仅一行，是一个既约分数(0写成0/1)，为小球... 查看详情
bzoj1867钉子和小球(代码片段)
题目链接简单$DP$$$dp[1][1]=1( ext显然)$$$$map[i][j]==‘*‘?dp[i+1][j]+=dp[i][j]/2,dp[i+1][j+1]+=dp[i][j]/2:dp[i+2][j+1]+=dp[i][j]$$如果直接输出概率这样就好，但是让写成分数咋整？开个结构体记录分子分母可以(好像大部分人这么做的)本宝宝一开始... 查看详情
[poj1189][bzoj1867][codevs1709]钉子和小球
...;Description有一个三角形木板,竖直立放，上面钉着n(n+1)/2颗钉子，还有(n+1)个格子（当n=5时如图1）。每颗钉子和周围的钉子的距离都等于d，每个格子的宽度也都等于d，且除了最左端和最右端的格子外每个格子都正对着最下面一排... 查看详情
bzojnoi1999钉子和小球动态规划+分数类
题目大意：不太好描写叙述，自己看吧。。思路：首先从最上面的点開始考虑。由于球一定是从最上面開始往下掉，所以球经过最上面的点的概率是1，然后他会有1/2的几率向左，1/2的几率向右，也就是以下的两个点均分上面点... 查看详情
poj1189钉子和小球
题目大意：一个三角形木板,竖直立放，上面钉着n(n+1)/2颗钉子，还有(n+1)个格子（当n=5时如图1）。每颗钉子和周围的钉子的距离都等于d，每个格子的宽度也都等于d，且除了最左端和最右端的格子外每个格子都正对着最下面一排... 查看详情
[noi1999]棋盘分割（推式子+dp）
http://poj.org/problem?id=1191棋盘分割TimeLimit: 1000MS MemoryLimit: 10000KTotalSubmissions: 15655 Accepted: 5556Description将一个８*８的棋盘进行如下分割：将原棋盘割下一块矩形棋盘并使剩下部分也是矩形，再将剩下的部分继续... 查看详情
bzoj1415:[noi2005]聪聪和可可[dp概率]
传送门题意：小兔子乖乖~~~题意·真：无向图吗，聪抓可，每个时间聪先走可后走，聪一次可以走两步，朝着里可最近且点编号最小的方向；可一次只一步，等概率走向相邻的点或不走求聪抓住可的期望时间 和游走很像... 查看详情
bzoj1415:[noi2005]聪聪和可可期望dp+bfs(代码片段)
因为边权为1所以a直接bfs瞎搞就行……我一开始竟然写了个spfa#include<iostream>#include<cstdio>#include<queue>#include<cstring>usingnamespacestd;constintN=1005,inf=1e9;intn,m,st,ed,h[N],cnt,a[N][N],b[N][N 查看详情
bzoj2037[sdoi2008]sue的小球区间dp+费用提前
【BZOJ2037】[Sdoi2008]Sue的小球DescriptionSue和Sandy最近迷上了一个电脑游戏，这个游戏的故事发在美丽神秘并且充满刺激的大海上，Sue有一支轻便小巧的小船。然而，Sue的目标并不是当一个海盗，而是要收集空中漂浮的彩蛋，Sue有一... 查看详情
bzoj4197noi2015寿司晚宴状压dp
4197:[Noi2015]寿司晚宴TimeLimit: 10Sec MemoryLimit: 512MBSubmit: 694 Solved: 440[Submit][Status][Discuss]Description为了庆祝NOI的成功开幕，主办方为大家准备了一场寿司晚宴。小G和小W作为参加NOI的选手，也 查看详情
bzoj4199[noi2015]品酒大会后缀自动机+dp
题意两个长度为$r$的子串相等称为$r$相似，两个$r$相似的权值等于子串开头位置权值乘积，给定字符串和每个位置权值，求$r$相似子串数量和最大权值乘积对反串建立后缀自动机得到后缀树，后缀树上两个状态的lca的长度len就是... 查看详情
bzoj24362436:[noi2011]noi嘉年华（区间dp）
2436:[Noi2011]Noi嘉年华DescriptionNOI2011在吉林大学开始啦！为了迎接来自全国各地最优秀的信息学选手，吉林大学决定举办两场盛大的NOI嘉年华活动，分在两个不同的地点举办。每个嘉年华可能包含很多个活动，而每个活动只能在一... 查看详情
●bzoj3672[noi2014]购票
...（树上CDQ分治...） 这里有一个没有距离限制的简单版：BZOJ1767[Ceoi2009]harbingers定义$DP[i]$为从i出发到1号点的最小花费，$dis_i$为i到1号点的距离：转移：$DP[i]=min(DP[j]+(dis_i- 查看详情
noi1999jzyzoj1289棋盘分割dp方差的数学结论
http://172.20.6.3/Problem_Show.asp?id=1289除了下标一坨一坨屎一样挺恶心其他都还挺容易的dp，这道题才发现scanf保留小数位是四舍五入的，惊了。f[k][x1][y1][x2][y2]嗯写的时候猜错结论了，本来以为是求下属分配方案中平方和与平均数平方... 查看详情
bzoj4944noi2017泳池
http://www.elijahqi.win/archives/3899考虑这个一定是一个从第0行开始连续的一个矩形直接求大小为K不可求那么不妨求小于等于K-小于等于K-1的即可那么设dp[i][j]表示宽度为i高度至少为j的概率i是多少那么dp[i][j]=0(i∗j>k)dp[i][j]=1... 查看详情
bzoj2435：[noi2011]道路修建（树型dp）
http://www.lydsy.com/JudgeOnline/problem.php?id=2435题意：中文题意。思路：很简单的树形DP，sz记录儿子有多少个和cur记录走的哪条弧，然后直接算就可以了。（时间有点紧）。1#include<cstdio>2#include<cmath>3#include<cstring>4#include<... 查看详情
bzoj1415[noi2005]聪聪和可可
【算法】期望DP,记忆化搜索 题目【题解】浅析竞赛中一类数学期望问题的解决方法 例题首先因为聪聪走的步数等于大于可可走的步数，所以不可能出现循环(高斯消元)，使DP成为可能。因为是图显然采用记忆化搜索。p[x][... 查看详情