聪明的kk
时间限制:1000 ms | 内存限制:65535 KB
难度:3
描述
聪明的“KK”
非洲某国展馆的设计灵感源于富有传奇色彩的沙漠中陡然起伏的沙丘,体现出本国不断变换和绚丽多彩的自然风光与城市风貌。展馆由五部分组成,馆内影院播放名为《一眨眼的瞬间》的宽银幕短片,反映了建国以来人民生活水平和城市居住环境的惊人巨变。
可移动“沙丘”变戏法 的灵感源于其独特而雄伟的自然景观——富于传奇色彩的险峻沙丘。宏伟的结构、可循环的建材,与大自然相得益彰。环绕一周,发现它正是从沙丘那不断变换的形态中汲取灵感的。外形逼真到无论从哪个角度去观察,都能清楚地辨识出沙丘的特征。
它“坡面”高达20米,微风吹来,你是否感觉到沙的流动?用手去触碰,却发现原来是“魔术戏法”。它表面的不锈钢面板呈现出一种富于变幻的色彩,从不同角度观察,呈现不同色泽,由此来模仿流动沙丘的光感。
走进第三展厅有一个超大的屏幕,通过奇妙的特效,让观众犹如亲身来到浩瀚的沙漠。更为奇妙的是,只见一个小动物“KK”正从沙漠区域(矩形)的左上角沿着向右或向下的方向往右下角跑去。KK太聪明了,它居然能在跑的过程中会选择吃掉尽可能多的虫子线路。
你知道它吃掉多少虫子吗?
输入
第一行:N M (1≤N M≤20 0≤Xij≤500(i=1,2„.N, j=1,2„,M)
)表示沙漠是一个N*M的矩形区域
接下来有N行:每行有M个正整数,Xi1 Xi2 ……Xim 表示各位置中的虫子数(单个空格隔开)
假设“KK”只能向右走或向下走。
输出
输出有一个整数, 表示“KK”吃掉最多的虫子数。
样例输入
3 4
3 1 2 8
5 3 4 6
1 0 2 3
样例输出
24
这道题很明显 用动态规划即可解决
#include<iostream>
using namespace std;
int main()
{
int r,l,i,j,sum;
int m[21][21]={0};
cin>>r>>l;
for(i=1;i<=r;i++)
for(j=1;j<=l;j++)
cin>>m[i][j];
for(i=1;i<=r;i++)
for(j=1;j<=l;j++)
{
m[i][j]+=m[i-1][j]>m[i][j-1]?m[i-1][j]:m[i][j-1];
}
cout<<m[i-1][j-1];
return 0;
}
<script type="text/javascript">
$(function () {
$('pre.prettyprint code').each(function () {
var lines = $(this).text().split('\n').length;
var $numbering = $('<ul/>').addClass('pre-numbering').hide();
$(this).addClass('has-numbering').parent().append($numbering);
for (i = 1; i <= lines; i++) {
$numbering.append($('<li/>').text(i));
};
$numbering.fadeIn(1700);
});
});
</script>
分享到:
相关推荐
【基于LINGO的优化问题动态规划法求解】 在运筹优化领域,LINGO是一款强大的数学建模软件,尤其适用于解决各种线性、非线性以及动态规划问题。不同于传统方法,LINGO甚至可以在没有明确目标函数的情况下解决动态...
动态规划求解方法的Matlab实现及应用 本文主要讲述了动态规划求解方法的Matlab实现及应用,涵盖了动态规划的基本概念、Matlab实现过程以及实践应用结果。 首先,动态规划是一种数学方法,用于解决多阶段决策问题。...
动态规划算法求解TSP 用动态规划算法求解TSP,数据为Solomon数据集的c101文件读取,可视化路径图,用图展示每次迭代的最优值、最差值和平均值,并与Gurobi求解结果比较各计算时间下的目标值。动态规划算法求解TSP 用...
动态规划求解并输出所有LCS
动态规划求解资源分配,给定设备数与车间数,按照自动生成的利润表,求解得出最优分配。
关于动态规划最短路径求解的matlab学习例子
在给出的Python代码中,`Solution` 类包含了TSP问题的动态规划求解过程。`__init__` 方法初始化类,接收距离矩阵`X`和起始节点`start_node`。`transfer` 方法用于将集合转换为二进制表示,方便在回溯矩阵中定位。`...
**C# 动态规划求解旅行商问题详解** 旅行商问题(Traveling Salesman Problem,简称TSP)是一个经典的组合优化问题,它涉及到寻找最短的可能路线,使得旅行商能够访问每个城市一次并返回起点。在计算机科学中,这个...
### 动态规划求解资源分配问题 #### 实验背景及目标 本实验旨在通过一个具体的案例——资源分配问题,来深入理解动态规划算法的设计思想及其应用。具体来说,研究如何将一定数量的设备(n台)最有效地分配给多个...
最大子段和问题,可参考《算法设计与分析》讲义中关于用动态规划策略求解最大子段和问题的思想设计动态规划算法。本算法用户需要输入元素个数n,及n个整数。程序应该给出良好的用户界面,输出最大子段相关信息,包括...
动态规划法求解生产与存储问题 动态规划是一种 mathematics 方法,用于解决多阶段决策过程的优化问题。它的发展可以追溯到 20 世纪 50 年代初期,当时美国数学家 R.E. Bellman 等人在研究多阶段决策过程的优化问题...
动态规划求解矩阵链乘
在Excel 2003中,规划求解是一项强大的数据分析工具,它允许用户解决复杂的优化问题,例如在满足一系列约束条件的情况下最大化或最小化某个目标函数。规划求解宏加载项是实现这一功能的关键组件,它扩展了Excel的...
Excel的规划求解插件,也称为"SOLVER",是Microsoft Office Excel中的一款强大工具,主要用于解决线性、非线性以及整数优化问题。它可以帮助用户在满足一系列约束条件下,找到最优的决策变量值,以最大化或最小化...
规划求解宏是Microsoft Office 2003中Excel组件的一个强大工具,它允许用户解决复杂的优化问题。在商业决策、工程设计、财务分析等领域,规划求解宏可以帮助找到最佳解决方案,例如最小化成本、最大化收益或满足特定...
总的来说,Matlab作为一款强大的科学计算工具,其灵活的编程环境使得动态规划问题的求解变得简单易行。通过对每个阶段的最优决策进行迭代计算,可以找到整个生产计划的最优解,从而实现成本最小化。在实际应用中,...
重点掌握:动态规划法求解每对结点之间的最短路径、0/1背包问题。 如果求任意两点之间的最短路径,两点之间可以直接到达但却不是最短的路径,要让任意两点(例如从顶点a点到顶点b)之间的路程变短,只能引入第三个点...
会议安排(贪心算法和动态规划) 会议安排问题是计算机科学中的一种经典问题,目的是在一系列活动中选择尽可能多的活动,使得每个活动的结束时间不早于下一个活动的开始时间。这个问题可以使用贪心算法和动态规划两...
动态规划的核心思想是自底向上地解决问题,通过建立状态转移方程来逐步求解。对于最大子段和问题,我们可以定义一个二维数组`dp`,其中`dp[i][j]`表示数组从索引`i`到`j`的最大子段和。对于单个元素,其最大子段和...