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写法#include <stdio.h> #include <string.h> #include <stdlib.h> #include <math.h> #include <iostream> #include <sstream> #include <algorithm> using namespace std; template<class T>inline T strTo(string s){istringstream is(s);T v;is>>v;return v;} template<class T>inline string toStr(const T& v){ostringstream os;os<<v;return os.str();} #define ep 1E-10 #define CLR(arr,v) memset(arr, v, sizeof(arr)) #define SQ(a) ((a)*(a)) #define DEBUG(a) printf("%s = %s\n", #a, toStr(a).c_str()) #define FOR(i,s,e) for( int (i)=(s); (i) < (e) ; i++) #define FIN(s) freopen(s,"r",stdin) #define FOUT(s) freopen(s,"w",stdout) typedef long long ll; ll gcd(ll a,ll b) { if (a < b) return gcd(b,a); ll c; while (b) c=a%b,a=b,b=c; return a; } ll lcm(ll a, ll b) { ll g = gcd(a,b); return a/g*b; } struct NODE { ll mol; ll den; NODE(ll m, ll d) {mol=m, den=d;} NODE(){mol=0;den=0;} NODE operator *(NODE a) { NODE k(0,0); if (mol == 0 || a.mol == 0) return k; ll g_m = gcd(mol, a.den); ll g_d = gcd(den, a.mol); k.mol = (mol/g_m)*(a.mol/g_d); k.den = (den/g_d)*(a.den/g_m); return k; } NODE operator +(NODE b) { NODE k(0,0); if (mol == 0) return b; if (b.mol == 0) { k.mol=mol,k.den=den; return k; } ll lcm_den = lcm(den,b.den); k.mol=lcm_den/den*mol+lcm_den/b.den*b.mol; k.den=lcm_den; ll g = gcd(k.mol,k.den); k.mol/=g; k.den/=g; return k; } }dp[60][60]; char s[60][60]; const NODE HF(1,2); char s_help[300]; int n,m; int main() { scanf("%d%d",&n,&m); getchar(); FOR(i,0,n) { gets(s_help); int kk=0; for (int k=0; s_help[k];k++) if (s_help[k] == '.' || s_help[k] == '*') s[i][kk++]=s_help[k]; s[i][kk]='\0'; } dp[0][0].den=dp[0][0].mol=1; FOR(i,1,n) { FOR(j,0,i+1) { if (j == 0) { if (s[i-1][j] == '*') dp[i][j]=dp[i-1][j]*HF; continue; } if (i == j) { if (s[i-1][j-1] == '*') dp[i][j]=dp[i-1][j-1]*HF; continue; } if (s[i-1][j] == '*') dp[i][j]=dp[i][j]+dp[i-1][j]*HF; if (s[i-1][j-1] == '*') dp[i][j]=dp[i][j]+dp[i-1][j-1]*HF; if (i-2>=0 && s[i-2][j-1] == '.') dp[i][j]=dp[i][j]+dp[i-2][j-1]; } } NODE ans = dp[n-1][m]*HF; if (m >= 1) ans = ans + dp[n-1][m-1]*HF; if (n >= 2 && s[n-2][m-1] == '.') ans = ans + dp[n-2][m-1]; if (ans.mol == 0) printf("0/1\n"); else printf("%lld/%lld\n",ans.mol,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