HDU 2391 Filthy Rich [수 탑 DP]

1233 단어
제목 링크:
http://acm.hdu.edu.cn/showproblem.php?pid=2391
제목 의 대의:
N * M 의 행렬 에서 서로 다른 위치 에 서로 다른 무게 의 황금 이 있 고 행렬 의 왼쪽 상단 부터 오른쪽으로 만 가능 합 니 다.
또는 아래로 내 려 가 왼쪽 상단 에서 오른쪽 하단 까지 가면 얼마나 많은 금 을 얻 을 수 있 느 냐 고 물 었 다.
생각:
간단 한 수 탑 DP, 상태 전이 방정식: dp [j] = max (dp [j - 1], dp [j]) + Map [i] [j].
AC 코드:
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;

int Map[1100][1100],dp[1100],N,M;

int main()
{
    int T,kase = 0;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&N,&M);
        for(int i = 1; i <= N; ++i)
        {
            for(int j = 1; j <= M; ++j)
            {
                scanf("%d",&Map[i][j]);
            }
        }

        for(int i = 1; i <= N; ++i)
        {
            for(int j = 1; j <= M; ++j)
            {
                if(i == 1)
                    dp[j] = dp[j-1] + Map[i][j];
                else
                    dp[j] = max(dp[j-1],dp[j])+ Map[i][j];
            }
        }
        printf("Scenario #%d:
",++kase); printf("%d

",dp[M]); } return 0; }

좋은 웹페이지 즐겨찾기