首页 > 分享 > 【NOI OJ】2728 摘花生

【NOI OJ】2728 摘花生

最新推荐文章于 2022-06-02 17:57:33 发布

weixin_30553065 于 2016-09-30 13:37:00 发布

2728:摘花生

总时间限制:  1000ms  内存限制:  65536kB 描述 Hello Kitty 想摘点花生送给她喜欢的米老鼠。她来到一片有网格状道路的矩形花生地(如下图),从西北角进去,东南角出来。地里每个道路的交叉点上都有种着一株花生苗,上面有若干颗花生,经过一株花生苗就能摘走该它上面所有的花生。Hello Kitty只能向东或向南走,不能向西或向北走。问Hello Kitty 最多能够摘到多少颗花生。

输入 第一行是一个整数T,代表一共有多少组数据。1<=T <= 100
接下来是T组数据。

每组数据的第一行是两个整数,分别代表花生苗的行数R和列数 C ( 1<= R,C <=100)
每组数据的接下来R行数据,从北向南依次描述每行花生苗的情况。每行数据有 C 个整数,按从西向东的顺序描述了该行每株花生苗上的花生数目 M ( 0<= M <= 1000)。

输出 对每组输入数据,输出一行,内容为Hello Kitty能摘到得最多的花生颗数。 样例输入

2 2 2 1 1 3 4 2 3 2 3 4 1 6 5 样例输出

8 16

#------------------------------------------------------------------------------#

很简单的动规题。

找出每个阶段最优解,和经典数塔问题很像。

思路:

每个点无非就是从它上面或者左边走过来,选择较大的一个就好。

状态转移方程:f[i][j]=max(f[i-1][j],f[i][j-1])

i-1,j即为从上面过来;i,j-1即为从左边过来。

最后输出出口处即可。

代码:

#include<cstdio>

#include<algorithm>

using namespace std;

int a[105][105],f[105][105];

int c,r,maxn;

int main()

{

int s;

scanf("%d",&s);

for(int i=0;i<s;i++)

{

scanf("%d%d",&c,&r);

for(int i=1;i<=c;i++)

for(int j=1;j<=r;j++)

{

scanf("%d",&a[i][j]);

f[i][j]=a[i][j];

}

for(int i=1;i<=c;i++)

for(int j=1;j<=r;j++)

f[i][j]+=max(f[i-1][j],f[i][j-1]);

printf("%dn",f[c][r]);

}

}

                                                                                              By WZY

转载于:https://www.cnblogs.com/LinqiongTaoist/p/7203766.html

相关知识

花生问题——百练OJ:2950:摘花生与1928:The Peanuts
SWUST oj 348: 花生采摘
百练2950:摘花生
西科大oj 花生采摘
swust oj 384花生采摘
SWUST OJ 348:花生采摘
本人的第一个简单动态规划小题(摘花生) c语言
swust oj 342变位词 348花生采摘413: Quick Sort430: 国名排序445: 选择问题
洛谷 P1086 花生采摘 题解
花生采摘

网址: 【NOI OJ】2728 摘花生 https://m.mcbbbk.com/newsview691391.html

所属分类:萌宠日常
上一篇: 你知道给狗吃什么健康吗?这4种喂
下一篇: 在哪能买到宠物猴?揭阳哪个地方有