Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

一个很常规的dp写法

Posted by Ly86 at 2011-02-01 17:53:36 on Problem 1189
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator