Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
破dp题,用int会爆!#include <iostream> #include <stdio.h> #include <string> using namespace std; struct frc{ long long int num; long long int den; frc(long long int n, long long int d): num(n), den(d){} frc(): num(1), den(1){} }; frc add(frc f1, frc f2){ if(f1.den < f2.den){ long long int b = f2.den/f1.den; return frc(f1.num * b + f2.num, f2.den); } if(f1.den > f2.den){ long long int b = f1.den/f2.den; return frc(f1.num + f2.num * b, f1.den); } long long int num = f1.num + f2.num; long long int den = f1.den; if(num == 0) return frc(0,1); while(num%2 == 0){ num /= 2; den /= 2; } return frc(num, den); } frc div2(frc f){ if(f.num == 0) return frc(0,1); return frc(f.num, f.den*2); } ostream& operator<<(ostream& out, frc f){ out << f.num << "/" << f.den << " "; return out; } int main() { int n, m; //scanf("%d%d", &n, &m); cin >> n >> m; bool d[60][60]; for(int i = 1; i <= n; i++){ string s; while(1){ getline(cin, s); if(s.length() > 0) break; } //cout << s.length() << endl; int idx = 0; for(int j = 0; ; j++){ if(s[j] == ' ') continue; if(s[j] == '*') d[i][idx] = 1; else if(s[j] == '.') d[i][idx] = 0; idx ++; if(idx == i) break; } } /* for(int i = 1; i <= n; i++){ for(int j = 0; j < i; j++){ cout << d[i][j] << " "; } cout << endl; }*/ frc p[60][120]; p[1][0] = frc(1,1); for(int i = 2; i <= n; i++){ for(int k = 0; k < i-1; k++){ if(d[i-1][k]) p[i][2*k+1] = frc(0,1); else p[i][2*k+1] = p[i-1][2*k]; } for(int k = 0; k < i; k++){ frc res(0,1); if(k > 0 && d[i-1][k-1]) res = add(res, div2(p[i-1][2*k-2])); if(k > 0 && k < i-1) res = add(res, p[i-1][2*k-1]); if(k < i-1 && d[i-1][k]) res = add(res, div2(p[i-1][2*k])); p[i][2*k] = res; } } /* for(int j = 1; j <= n; j++){ for(int i = 0; i <= 2*j-2; i++){ cout << p[j][i]; } cout << endl; } cout << endl; */ frc ans(0,1); if(m != 0) ans = add(ans, div2(p[n][2*m-2])); if(m != 0 && m != n) ans = add(ans, p[n][2*m-1]); if(m != n) ans = add(ans, div2(p[n][2*m])); printf("%I64d/%I64d\n", ans.num, ans.den); return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator