首页 > 代码库 > [bzoj1867][Noi1999][钉子和小球] (动态规划)
[bzoj1867][Noi1999][钉子和小球] (动态规划)
Description
Input
第1行为整数n(2<=n<=50)和m(0<=m<=n)。以下n行依次为木板上从上至下n行钉子的信息,每行中‘*’表示钉子还在,‘.’表示钉子被拔去,注意在这n行中空格符可能出现在任何位置。
Output
仅一行,是一个既约分数(0写成0/1),为小球落在编号为m的格子中的概pm。既约分数的定义:A/B是既约分数,当且仅当A、B为正整数且A和B没有大于1的公因子。
Sample Input
5 2
Sample Output
7/16
Solution
设f[i][j]代表小球落到位置为(i,j)的概率,分数求解即可
#include <stdio.h>#define L long long#define RG registerinline 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;}
[bzoj1867][Noi1999][钉子和小球] (动态规划)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。