[bzoj1867][noi1999][钉子和小球](动态规划)

关键词：

Description

Input

Output

Sample Input

5 2

Sample Output

Solution

设f[i][j]代表小球落到位置为(i,j)的概率，分数求解即可

#include <stdio.h>
#define L long long
#define RG register

inline void Rin(RG int &x) {
  x=0;RG int c=getchar(),f=1;
  for(;c<48||c>57;c=getchar())
    if(!(c^45))f=-1;
  for(;c>47&&c<58;c=getchar())
    x=(x<<1)+(x<<3)+c-48;
  x*=f; }

inline void ploy(RG bool &x) {
  RG char c=getchar();
  while(c!=‘*‘&&c!=‘.‘)c=getchar();
  x=c==‘*‘?true:false; }

void Shiki(RG L x) {
  if(!x)return;
  Shiki(x/10);
  putchar(x%10+48); }

L gcd(RG L a,RG L b) {
  return b?gcd(b,a%b):a; }

bool _map[55][55];

int n,m;

struct fr{
  L n,d;

  fr(RG L _=0,RG L __=1) : n(_),d(__) {} }f[55][55];

inline void rec(fr &_this) {
  L t=gcd(_this.n,_this.d);
  _this.n/=t;
  _this.d/=t; }

fr operator + (const fr &a,const fr &b) {
  fr res;
  L t=gcd(a.d,b.d);
  res.n=b.d/t*a.n+a.d/t*b.n;
  res.d=a.d/t*b.d;
  return res; }

fr operator * (const fr &a,const fr &b) {
  fr res(a.n*b.n,a.d*b.d);
  rec(res);
  return res; }

void operator += (fr &a,const fr &b) {
  a=a+b; }

int main() {
  Rin(n),Rin(m);
  for(RG int i=1; i<=n; i++)
    for(RG int j=1; j<=i; j++)
      ploy(_map[i][j]);
  f[1][1]=fr(1,1);
  for(RG int i=1; i<=n; i++)
    for(RG int j=1; j<=i; j++)
      rec(f[i][j]),
      _map[i][j]?
    f[i+1][j]+=f[i][j]*fr(1,2),f[i+1][j+1]+=f[i][j]*fr(1,2):
    f[i+2][j+1]+=f[i][j];
  rec(f[n+1][m+1]);
  Shiki(f[n+1][m+1].n); putchar(‘/‘); Shiki(f[n+1][m+1].d);
  return 0;
}

bzoj千题计划189：bzoj1867:[noi1999]钉子和小球

http://www.lydsy.com/JudgeOnline/problem.php?id=1867 dp[i][j]落到（i，j）的方案数dp[i][j]=0.5*dp[i-1][j] [(i-1,j)位置有钉子]+0.5*dp[i-1][j-1]  [（i-1.j-1）位置有钉子]+dp[i-1][j-2]  [（i-1，j-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 查看详情

[poj1189][bzoj1867][codevs1709]钉子和小球

...;Description有一个三角形木板,竖直立放，上面钉着n(n+1)/2颗钉子，还有(n+1)个格子（当n=5时如图1）。每颗钉子和周围的钉子的距离都等于d，每个格子的宽度也都等于d，且除了最左端和最右端的格子外每个格子都正对着最下面一排... 查看详情

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]$$如果直接输出概率这样就好，但是让写成分数咋整？开个结构体记录分子分母可以(好像大部分人这么做的)本宝宝一开始... 查看详情

bzojnoi1999钉子和小球动态规划+分数类

题目大意：不太好描写叙述，自己看吧。。思路：首先从最上面的点開始考虑。由于球一定是从最上面開始往下掉，所以球经过最上面的点的概率是1，然后他会有1/2的几率向左，1/2的几率向右，也就是以下的两个点均分上面点... 查看详情

poj1189钉子和小球

题目大意：一个三角形木板,竖直立放，上面钉着n(n+1)/2颗钉子，还有(n+1)个格子（当n=5时如图1）。每颗钉子和周围的钉子的距离都等于d，每个格子的宽度也都等于d，且除了最左端和最右端的格子外每个格子都正对着最下面一排... 查看详情

bzoj1415:[noi2005]聪聪和可可

1#include<cstdio>2#include<iostream>3#include<cstring>4#include<algorithm>5#include<queue>6#definepapair<int,int>7#defineM10088#defineinf1000000009usingnamespacestd 查看详情

bzoj1415:[noi2005]聪聪和可可

1415:[Noi2005]聪聪和可可TimeLimit:10Sec  MemoryLimit:162MBSubmit:2037  Solved:1191[Submit][Status][Discuss]DescriptionInput数据的第1行为两个整数N和E，以空格分隔，分别表示森林中的景点数和连接相邻景点的路的条数。第2行包含两个整... 查看详情

bzoj1415:[noi2005]聪聪和可可

直接上记忆化搜索#include<queue>#include<cstdio>#include<algorithm>usingnamespacestd;intread_p,read_ca;inlineintread(){read_p=0;read_ca=getchar();while(read_ca<‘0‘||read_ca>‘9‘)read_ca= 查看详情

bzoj1415noi2005聪聪和可可（动态规划，数学期望）

【BZOJ1415】【NOI2005】聪聪和可可（动态规划，数学期望）题面BZOJ题解先预处理出当可可在某个点，聪聪在某个点时聪聪会往哪里走然后记忆化搜索一下就好了#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>... 查看详情

[noi1999]生日蛋糕

题目：洛谷P1731、VijosP1297、codevs1710。题目大意：让你做一个体积为$Npi$的每层都是圆柱的蛋糕，m层，且从下到上每层的高度和半径都不超过下面一层的，且是整数。设表面积Q=$Spi$，问你最小的S是多少（不可能输出0）。解题思... 查看详情

bzoj1415[noi2005]聪聪和可可

TimeLimit: 10Sec  MemoryLimit: 162MBSubmit: 1586  Solved: 929DescriptionInput数据的第1行为两个整数N和E，以空格分隔，分别表示森林中的景点数和连接相邻景点的路的条数。第2行包含两个整数C和M，以空格分隔，分... 查看详情

bzoj1415:[noi2005]聪聪和可可

题面BzojSol就是求期望预处理出可可在某一位置时聪聪下一步怎么走然后按题意模拟，记搜#include<bits/stdc++.h>#defineRGregister#defineILinline#defineFill(a,b)memset(a,b,sizeof(a))usingnamespacestd;typedeflonglongll;constint_(2005);ILllIn 查看详情

bzoj1415noi2005聪聪和可可

%%%http://hzwer.com/2819.html先各种暴力搞出来p[x][y]（从x到y下一个最近应该到达的位子）然后就记忆化搜索？？（雾）1#include<bits/stdc++.h>2#defineLLlonglong3#defineLDlongdouble4#defineN1000055usingnamespacestd;6inlineintra()7{8intx=0 查看详情

bzoj1509[noi2003]逃学的小孩直径

【BZOJ1509】[NOI2003]逃学的小孩DescriptionInput第一行是两个整数N（3?N?200000）和M，分别表示居住点总数和街道总数。以下M行，每行给出一条街道的信息。第i+1行包含整数Ui、Vi、Ti（1?Ui,Vi?N，1?Ti?1000000000），表示街道i连接居住点Ui和Vi... 查看详情

bzoj14151415:[noi2005]聪聪和可可（bfs+记忆化搜索+期望）

1415:[Noi2005]聪聪和可可TimeLimit: 10Sec  MemoryLimit: 162MBSubmit: 1640  Solved: 962DescriptionInput数据的第1行为两个整数N和E，以空格分隔，分别表示森林中的景点数和连接相邻景点的路的条数。第2行包含两个整数... 查看详情

bzoj1415noi2005聪聪和可可

题目链接：聪聪和可可　　一道水题……开始还看错题了，以为边带权……强行(O(n^3))预处理……　　首先，我们显然可以预处理出一个数组(p[u][v])表示可可在点(u)，聪聪在点(v)的时候聪聪下一步会往哪里走。然后……一个记忆... 查看详情

bzoj2007:[noi2010]海拔

2007:[Noi2010]海拔TimeLimit: 20Sec  MemoryLimit: 552MBSubmit: 2410  Solved: 1142[Submit][Status][Discuss]DescriptionYT市是一个规划良好的城市，城市被东西向和南北向的主干道划分为n×n个区域。简单 查看详情