hdu 2084——数え塔

住所
http://acm.hdu.edu.cn/showproblem.php?pid=2084
位置

シンプルダイナミックプログラム

水問題

分析

はボトムアップして問題を解いて、グローバル最適解は必ず局所最適解を含みます.
dp[i][j]=max(dp[i＋1][j],dp[i＋1][j＋1]+a[i][j]

空間最適化:1つの配列だけを開発し、元の配列上で状態更新を行う必要があります.
a[i][j]+=max(a[i＋1][j],a[i＋1][j＋1]

コード

#include 
#include 

int main()
{
    int size = 0;
    int n = 0;
    int i = 0;
    int j = 0;
    int a[100][100];

    scanf("%d%*c",&size);
    while(size--)
    {
        memset(a,0,10000*sizeof(int));
        scanf("%d%*c",&n);
        for(i=0;ifor(j=0;j<=i;j++)
            {
                scanf("%d%*c",&a[i][j]);
            }
        }
        for(i=n-2;i>=0;i--)
        {
            for(j=0;j<=i;j++)
            {
                a[i][j] += a[i+1][j]>a[i+1][j+1]?a[i+1][j]:a[i+1][j+1];
            }
        }
        printf("%d
",a[0][0]);
    }
    return 0;
}

パフォーマンス
Exe.Time
Exe.メモリ
Code Length
Language
31 MS
1728 K
664 B
c
締め括りをつける

は複数の試験例の問題を有し、記憶空間のデータ整理

に注意する.

scanf()を使用する場合、データ間隔(スペース、改行など)に注意する処理

後記
素朴なトップダウンで検索する方法を採用していますが、本題でも通ります.

#include 
#include 
#define MAX(x,y) ((x)

int main()
{
    int size = 0;
    int n = 0;
    int fr = 0;
    int temp = 0;
    int i = 0;
    int j = 0;
    int result[5050] = {-1};

    scanf("%d%*c",&size);
    while(size--)
    {
        scanf("%d%*c",&n);
        scanf("%d%*c",&result[0]);
        for(i=1;i1)*i/2;
            for(j=0;j<=i;j++)
            {
                scanf("%d%*c",&temp);
                if(j == 0)
                {
                    result[fr+j] = result[fr-i] + temp;
                }
                else if(j == i)
                {
                    result[fr+j] = result[fr-1] + temp;
                }
                else
                {
                    result[fr+j] = MAX(result[fr-i+j-1],result[fr-i+j]) + temp;
                }
            }
        }
        for(i=1;iif(result[fr+i] > result[fr])
            {
                result[fr] = result[fr+i];
            }
        }
        printf("%d
",result[fr]);
    }
    return 0;
}

Exe.Time
Exe.メモリ
Code Length
Language
78 MS
1700 K
1139 B
c