LightOJ 1004 （dp）

http://acm.hust.edu.cn/vjudge/contest/121396#problem/F

分析：典型dp，但是这个图形是菱形，一开始没觉得菱形有什么不对，但是后来发现菱形的话，上下两个三角形dp的方式是不一样的。。

#include <iostream>
#include <cstdio>
#include <stdio.h>
#include <string.h>
using namespace std;
typedef long long LL;
#define maxn 210
int  dp[maxn][maxn], a[maxn][maxn];
int n;


int main()
{
    int T, t=1;

    scanf("%d", &T);

    while(T --)
    {
        scanf("%d", &n);

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

        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=i; j++)
                scanf("%d", &a[i][j]);
        }

        int k = n-1;

        for(int i=n+1; i<2*n; i++)
        {
            for(int j=1; j<=k; j++)
                scanf("%d", &a[i][j]);
            k--;
        }

        dp[1][1] = a[1][1];

        for(int i=1; i<n; i++)
        {
            for(int j=1; j<=n; j++)
            {
                dp[i+1][j]=max(dp[i][j], dp[i][j-1])+a[i+1][j];
            }
        }


        for(int i=n; i<2*n-1; i++)
        {
            for(int j=1; j<=n; j++)
            {
                dp[i+1][j]=max(dp[i][j], dp[i][j+1])+a[i+1][j];
            }
        }

     printf("Case %d: %d
",t++,dp[2*n-1][1]);

    }

    return 0;
}