寒假前几天有些懈怠,今深刻反思。

协会留的作业之一, 虽然一眼就看出了是一个动态规划问题,但是还是因为格式问题困扰好久,主要原因还是自己有些懈怠了

做题有些不熟练。要好好反思一下了。

问题描述:

有 m 颗质量大小不同的石子,从最下面一层开始堆石子,最下面一层放置 n 颗石子,每层减少一颗石子,恰好到最上一层为 一颗 石子。现在从最下面一层开始每层石子中取出一颗石子(注意,为了方便取出,要求只能拿和已拿石子相邻的两颗石子中的一颗),求能取出的石子质量和最大为多少?

输入:

石子总数 m(1≤m≤400) 
接下来每行表示从最下面一层开始每层每个石子的质量 w(1≤w≤108)

输出:

能取出的最大石子质量和

样例:

input

6
1 4 6
3 2
1

output

9

提示

   1
  2 3
 4 5 6
7 8 9 10

如果你拿了8,那么你就只能拿4或者5而不能拿6*

code:

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN = 400+7;

int num[MAXN][MAXN];
LL dp[MAXN][MAXN];

int main()
{
    int n;
    scanf("%d", &n);
    int cnt = 0;
    int k = 0;
    while(cnt < n)      // 获取行数保存到k
    {
        k++;
        cnt += k;
    }
    for(int i=1; i<=k; i++)     // 倒三角的形式输入
    {
        for(int j=1; j<=k-i+1; j++)
        {
            scanf("%d", &num[i][j]);
        }
    }
    memset(dp, 0, sizeof(dp));
    for(int j=1; j<=k; j++)     // 第一行的值就是num中第一行的值
        dp[1][j] = num[1][j];
    for(int i=1; i<=k; i++)
    {
        for(int j=1; j<=k-i+1; j++)
        {
            dp[i][j] = num[i][j] + max(dp[i-1][j], dp[i-1][j+1]);
            //printf("%d ", dp[i][j]);
        }
       // printf("\n");
    }
    printf("%lld\n", dp[k][1]);



    return 0;
}