POJ 1163: Triangle(동적 계획)

3145 단어 POJ
제목 전송문: POJ 1163: The Triangle
단순 동태 기획, 사고방식: 표 작성
#include 
#include 
using namespace std;
const int maxSize = 105;
int n;
int arr[maxSize][maxSize];
int d[maxSize][maxSize];

void readInput(int n) //      
{
    for (int i = 0; i < n; i++)
        for (int j = 0; j <= i; j++)
            cin >> arr[i][j];
}

void showInput(int n) //         
{
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j <= i; j++)
            cout << d[i][j];
        cout << "
"
; } } int maxSum(int i, int j) { if (n == i) return 0; // , 0 if (d[i][j] >= 0) return d[i][j]; // 0, , return d[i][j] = arr[i][j] + max(maxSum(i+1,j), maxSum(i+1,j+1)); // } int main() { while (cin >> n) { memset(d, -1, sizeof(d)); // -1 readInput(n); cout << maxSum(0, 0) << endl; //showInput(n); } return 0; }

좋은 웹페이지 즐겨찾기