1163 The Triangle 동적 계획

934 단어
/**
*    :     。。    ,      ,  sum  。
*
*         ,     。
*      dp。
*       ,           
*      dp[1]  
*/

#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <algorithm>
#define INF 0x7fffffff
#define MAXS none
#define LL long long
using namespace std;
int num[101][101], dp[101], ans;

void dpf(int r) {
    for(int i = r; i >= 1; i --) 
        for(int j = 1; j <= i; j ++) 
            dp[j] = dp[j] > dp[j + 1] ? dp[j] + num[i][j] : dp[j + 1] + num[i][j];
}

int main()
{
    int r;
    while(scanf("%d", &r) != EOF) {
        ans = 0;
        for(int i = 1; i <= r; i ++)
            for(int j = 1; j <= i; j ++)
                scanf("%d", &num[i][j]);
        memset(num[r + 1], 0, sizeof(num[r + 1]));
        dpf(r);
        printf("%d
", dp[1]); } return 0; }

좋은 웹페이지 즐겨찾기