首页 > 代码库 > poj 3176 Cow Bowling

poj 3176 Cow Bowling

题目链接:http://poj.org/problem?id=3176

 

思路:

基本的DP题目;将每个节点视为一个状态,记为B[i][j], 状态转移方程为 B[i][j] = A[i][j] + Max( B[i+1][j], B[i+1][j+1] );

代码:

 

#include <stdio.h> const int MAX_N = 350 + 10;int A[MAX_N][MAX_N], B[MAX_N][MAX_N];int Max( int a, int b ) { return a > b ? a : b; }int dp( int i, int j ){    if ( B[i][j] >= 0 )        return B[i][j];    return B[i][j] = A[i][j] + Max( dp(i+1, j), dp(i+1, j+1) );}int main(){    int n, ans;    scanf( "%d", &n );    for ( int i = 1; i <= n; ++i )        for ( int j = 1; j <= i; ++j )        {            scanf( "%d", &A[i][j] );            B[i][j] = -1;        }    for ( int k = 1; k <= n; ++k )        B[n][k] = A[n][k];    ans = dp( 1, 1 );    printf( "%d\n", ans );    return 0;}

 

poj 3176 Cow Bowling