首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。