HDU 2084 수 탑 DP 문제

수 탑 시간 제한: 1000 / 1000 MS (Java / Others)   Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 33706    Accepted Submission (s): 20119 Problem Description DP 알고리즘 을 설명 할 때 하나의 전형 적 인 예 는 바로 수 탑 문제 입 니 다. 이것 은 다음 과 같이 묘사 한 수 탑 이 있 습 니 다. 꼭대기 에서 끝까지 가 야 합 니 다. 만약 에 한 걸음 에 인접 한 결점 까지 만 갈 수 있다 면 지나 간 결점 의 숫자 와 최대 가 얼마 입 니까?이미 말씀 드 렸 는데, 이것 은 DP 의 문제 입 니 다. 당신 은 AC 를 할 수 있 습 니까?  Input 입력 데 이 터 는 먼저 하나의 정수 C 를 포함 하고 테스트 인 스 턴 스 의 개 수 를 표시 합 니 다. 각 테스트 인 스 턴 스 의 첫 줄 은 하나의 정수 N (1 < = N < = 100) 으로 수 탑의 높이 를 표시 합 니 다. 그 다음 에 N 줄 숫자 로 수 탑 을 표시 합 니 다. 그 중에서 i 줄 은 i 개의 정수 가 있 고 모든 정 수 는 구간 [0, 99] 안에 있 습 니 다.  Output 은 모든 테스트 인 스 턴 스 에 대해 출력 이 얻 을 수 있 는 최대 와 모든 인 스 턴 스 의 출력 이 한 줄 을 차지 합 니 다.  Sample Input 1 5 7 3 8 8 1 0  2 7 4 4 4 5 2 6 5   Sample Output 30  

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string>
#include <string.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <iomanip>
#include <time.h>
#include <set>
#include <map>
#include <stack>
using namespace std;
typedef long long LL;
const int INF=0x7fffffff;
const int MAX_N=10000;

int T,N;
int A[109][109];
int dp[109][109];
int main(){
    cin>>T;
    while(T--){
        scanf("%d",&N);
        for(int i=1;i<=N;i++){
            for(int j=1;j<=i;j++){
                scanf("%d",&A[i][j]);
            }

        }
        memset(dp,0,sizeof(dp));

        for(int i=N;i>=1;i--){
            for(int j=1;j<=i;j++){
                dp[i][j]=max(dp[i+1][j]+A[i][j],dp[i+1][j+1]+A[i][j]);
            }
        }
        cout<<dp[1][1]<<endl;
    }
    return 0;
}