首页 > 代码库 > BZOJ NOI 1999 钉子和小球 动态规划+分数类
BZOJ NOI 1999 钉子和小球 动态规划+分数类
题目大意:不太好描述,自己看吧。。
思路:首先从最上面的点开始考虑,因为球一定是从最上面开始往下掉,所以球经过最上面的点的概率是1,然后他会有1/2的几率向左,1/2的几率向右,也就是下面的两个点均分上面点的几率。当然这是所有的点都存在的情况。如果有哪里的点不存在了,那么求落到这个点的几率不变,然后它的所有几率都会加在在它下面两行且在正下方的点。
按照这样写dp方程,显然是不难的。之后就是恶心的输出了。两个方案,1.遇到小数就*2,保证它是整数。但是最高有50层,就要考虑一下2^50这么大,加上一些复杂的情况,很可能爆掉__int64,舍弃这种方法。2.就是写一个分数类。。这玩应还是第一次写,挺有趣的。。
CODE:
#include <cstdio> #include <iomanip> #include <cstring> #include <iostream> #include <algorithm> #define MAX 100 using namespace std; long long Gcd(long long x,long long y) {return y ? Gcd(y,x % y):x;} struct Fraction{ long long up; long long down; Fraction(long long _ = 0,long long __ = 1):up(_),down(__) {} void Reduction() { long long gcd = Gcd(up,down); up /= gcd; down /= gcd; } Fraction operator +(const Fraction &a)const { Fraction re; long long gcd = Gcd(down,a.down); re.down = a.down / gcd * down; re.up = (up * a.down + a.up * down) / gcd; re.Reduction(); return re; } Fraction operator +=(const Fraction &a) { *this = *this + a; return *this; } Fraction operator *(const Fraction &a)const { Fraction re(up * a.up,down * a.down); re.Reduction(); return re; } }; int cnt,ask; char map[MAX][MAX]; Fraction f[MAX][MAX]; inline char Judge(); int main() { cin >> cnt >> ask; for(int i = 1;i <= cnt; ++i) for(int j = 1;j <= i; ++j) map[i][j] = Judge(); f[1][1] = Fraction(1,1); for(int i = 1;i <= cnt; ++i) for(int j = 1;j <= cnt; ++j) { if(map[i][j] == '*') { f[i + 1][j] += f[i][j] * Fraction(1,2); f[i + 1][j + 1] += f[i][j] * Fraction(1,2); } else f[i + 2][j + 1] += f[i][j]; } printf("%lld/%lld",f[cnt + 1][ask + 1].up,f[cnt + 1][ask + 1].down); return 0; } inline char Judge() { char c; while(c = getchar()) { if(c == '*') return '*'; else if(c == '.') return '.'; } }
BZOJ NOI 1999 钉子和小球 动态规划+分数类
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。