FOJ 1004 Number Triangle

업데이트:2014-02-08 새벽.
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
원본:http://acm.fzu.edu.cn/problem.php?pid=1004
개술:수치 피 라 미 드 를 주 고 위 에서 아래로,어떻게 가 는 지,지나 가 는 수량 과 최대 치 를 물 어 봅 니 다.
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
분석 하 다.
'와 전 된 것'으로 추정 된다.인터넷 에 퍼 진 대부분의 해법 은 피라미드 가 아래 에서 위로 올 라 가 고 2 차원 배열 로 저장 된다.나 는 원래 단일 차원 배열 로 저장 해서 메모 리 를 비교적 절약 했다.나중에 이 문 제 는 사실 매우 간결 한 해법 이 있다 는 것 을 발견 하 였 다.
동적 계획 은 데 이 터 를 가 져 오 면서 연산 할 수 있 습 니 다.모든 줄 에서 첫 줄 에서 이 점 까지 의 최 적 화 된 값 으로 업 데 이 트 됩 니 다.마지막 줄 의 최대 치 를 판단 하면 됩 니 다.
이 문제 의 간단 한 변형 은 구 화의 최소 값 으로 바 꾸 는 것 이다.18 줄 의 함 수 를 로 바 꾸 기만 하면 된다.min 이면 됩 니 다.VC+로 제출 하 십시오.VC 가에 있어 야 가 있 습 니 다.max,__min 매크로 정의.

#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;

int main()
{
    int n, i, j, now;
    while (scanf("%d", &n) != EOF)
    {
        int a[2][1001] = {0};
        for (now = i = 1; i <= n; i++)
        {
            now ^= 1;
            for (j = 1; j <= i; j++)
            {
                scanf("%d", &a[now][j]);
                a[now][j] += __max(a[now^1][j-1], a[now^1][j]);
            }
        }
        printf("%d
", *max_element(&a[now][1], &a[now][n+1]));
    }
    return 0;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

ACM - 계산 기하학 적 Pick - up sticks -- poj 2653

Description Stan has n sticks of various length. The data for each case start with 1 <= n <= 100000, the number of stick...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

FOJ 1004 Number Triangle

좋은 웹페이지 즐겨찾기