| ||||||||||
| 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