寒假前几天有些懈怠,今深刻反思。
协会留的作业之一, 虽然一眼就看出了是一个动态规划问题,但是还是因为格式问题困扰好久,主要原因还是自己有些懈怠了
做题有些不熟练。要好好反思一下了。
问题描述:
有 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;
}