数塔的变形

2024-06-08 18:48
文章标签 变形 数塔

本文主要是介绍数塔的变形,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

聪明的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>
#include<string.h>
using namespace std;
int main()
{int a[40][40];memset(a,0,sizeof(a));int m,n;cin>>m>>n;int i,j,t=0;for(j=0;j<m;j++){t=j;for(i=0;i<n;i++,t++)cin>>a[t][i];}for(i=n+n-3;i>=0;--i)  {  for(j=0;j<=i;j++)  {  if(a[i][j]+a[i+1][j]>a[i][j]+a[i+1][j+1])  a[i][j]+=a[i+1][j];  else  a[i][j]+=a[i+1][j+1];  }  }  cout<<a[0][0]<<endl;  return 0;  }


也可以用dp[k][x1]表示第k步即第k条斜线上横坐标为x1时的最优解

x1+y1=k;

状态转移方程为:

dp[k][x1]=max(dp[k-1][x1-1],dp[k-1][x1])+map[x1][y1]  

时间对比:上一个是下边代码的结果


833780向往蓝天的鱼聪明的kkAccepted0252C/C++04-24 09:24:21
566808
向往蓝天的鱼聪明的kkAccepted4232C/C++09-21 20:39:56

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 52int dp[N][N],map[N][N];int main(){int m,n;while(cin>>m>>n){int i,j;for(i=1;i<=m;++i)for(j=1;j<=n;++j)cin>>map[i][j];memset(dp,0,sizeof(dp));int all=m+n;int k,t1=0,t2=0,ans=0;int x1,y1,x2,y2;dp[2][1]=map[1][1];for(k=2;k<=all;++k)for(x1=1;x1<=m;++x1){	y1=k-x1;	if(y1<0||y1>n)continue;dp[k][x1]=max(dp[k-1][x1-1],dp[k-1][x1])+ map[x1][y1] ;}cout<<dp[all][m]<<endl;}return 0;}

可以优化为滚动数组:内存稍微减少点

833810向往蓝天的鱼聪明的kkAccepted0232C/C++04-24 09:38:20

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 22int dp[2][N],map[N][N];int main(){int m,n;while(cin>>m>>n){int i,j;for(i=1;i<=m;++i)for(j=1;j<=n;++j)cin>>map[i][j];memset(dp,0,sizeof(dp));int all=m+n;int k,t1=0,t2=0,ans=0;int x1,y1,x2,y2;dp[2][1]=map[1][1];for(k=2;k<=all;++k)for(x1=1;x1<=m;++x1){	y1=k-x1;	if(y1<0||y1>n)continue;dp[(k+1)%2][x1]=max(dp[k%2][x1-1],dp[k%2][x1])+ map[x1][y1] ;}cout<<dp[(all+1)%2][m]<<endl;}return 0;}

#include<iostream>  
#include<cstring>  
#include<algorithm>
using namespace std;  
int a[25][1005],dp[25][1005];  //dp[i][j]表示前I行第j列的最优值
int main()  
{  int m,n;  while(cin>>m>>n){memset(dp,0,sizeof(dp)); memset(a,0,sizeof(a));int i,j,t=0,k;  for(i=1;i<=m;++i)for(j=1;j<=n;++j)cin>>a[i][j];/*for(i = 0; i<=m; i++)  dp[i][0] = -99999999;  for(i = 0; i<=n; i++)  dp[0][i] = -99999999;  dp[1][0] = dp[0][1] = 0; */ for(i=1;i<=m;++i)    {    for(j=1;j<=n;j++)    {  dp[i][j]=max(dp[i-1][j],dp[i][j-1]);//for(k=2;k<=n;++k)//if(j%k==0)//	 dp[i][j]=max(dp[i][j],dp[i][j/k]);dp[i][j]+=a[i][j];} }    cout<<dp[m][n]<<endl;   }return 0;    
} 


这篇关于数塔的变形的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1043011

相关文章

csu(背包的变形题)

题目链接 这是一道背包的变形题目。好题呀 题意:给n个怪物,m个人,每个人的魔法消耗和魔法伤害不同,求打死所有怪物所需的魔法 #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>//#include<u>#include<map

hdu3389(阶梯博弈变形)

题意:有n个盒子,编号1----n,每个盒子内有一些小球(可以为空),选择一个盒子A,将A中的若干个球移到B中,满足条件B  < A;(A+B)%2=1;(A+B)%3=0 这是阶梯博弈的变形。 先介绍下阶梯博弈: 在一个阶梯有若干层,每层上放着一些小球,两名选手轮流选择一层上的若干(不能为0)小球从上往下移动,最后一次移动的胜出(最终状态小球都在地面上) 如上图所示,小球数目依次为

跳台阶(动态规划/斐波那契变形)

跳台阶 链接:https://www.nowcoder.com/acm/contest/90/A来源:牛客网 题目描述 小明在坐景驰科技研发的无人车到达了目的地。 景驰科技(JingChi.ai)是一家由人工智能技术驱动、以无人驾驶技术为核心的智能出行公司。它将打造面向中国市场的全无人驾驶。 从无人车下来以后,小明看到了一个长长的楼梯。 有一个n级台阶的楼梯,小明一次可以向上跳1

Bellman_Ford变形求最长路+正权回路或spfa——POJ 1860

对应POJ题目:点击打开链接 Currency Exchange Time Limit: 1000MS Memory Limit: 30000KTotal Submissions: 20814 Accepted: 7451 Description Several currency exchange points are working in our city. L

[android总结]Zxing二维码扫描图片变形

关于使用ZXing扫描二维码图片变形的问题,晚上有很多种解释,但都是一个模板,经过多种尝试,还是没能解决我的问题。于是就自己研究,不过索性解决了,再次简单分享一下。 如果想在应用里添加自己的我二维码扫描功能,可以参照:http://blog.csdn.net/xiaanming/article/details/10163203   这篇博客描述的很详尽。 首先,你应该知道

Android 图片放错位置会拉伸变形

今天做了一个很小的需求,然后需要图片,我给ui要图片。直接给了我三套,还命名 x . xx. 2k 真的一开始都不知道。没有玩过这么正规的。我就用了一张,放到了hdpi下面。 后来同事帮我才知道, 图片要放到xhdip 里面,那样才不会拉伸变形。因为我们适配的分辨率很高。 现在的分辨率都是最低720,普遍1080。 我这才知道自己过时了。 然后放到正确的文件夹下,嗯,可以正常显示了。 x

【HDU4507】【吉哥系列故事——恨7不成妻】【变形数位dp】

吉哥系列故事——恨7不成妻 Time Limit: 1000/500 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others) Total Submission(s): 2260    Accepted Submission(s): 660 Problem Description 单身!   依然单

android 搜索栏滑动跟随缩放和移动,缩放变形问题

这两天新版界面改版,有个页面要求搜索栏跟随滑动会位移和缩放, 心想这还不简单么,具体如下是实现好的效果:    心想这还不简单么,第一想法是用 recyclerView.addOnScrollListener 计算好Y轴移动的距离和x缩放值再根据这些算出X轴偏移位置不就ok了么。 想法总是美好的,现实总是残酷的,view自带的setScale 缩放后导致搜索栏里的文字和图片同时放大

数塔 动态规划

Problem Description 在讲述DP算法的时候,一个经典的例子就是数塔问题,它是这样描述的: 有如下所示的数塔,要求从顶层走到底层,若每一步只能走到相邻的结点,则经过的结点的数字之和最大是多少? 已经告诉你了,这是个DP的题目,你能AC吗? Input 输入数据首先包括一个整数C,表示测试实例的个数,每个测试实例的第一行是一个整数N(1 <= N <= 100

CSS3 渐变、变形、过渡、动画小结

CSS3 渐变(IE9&-用滤镜filter来兼容) 线性渐变: linear-gradient([ [ <angle> | to <side-or-corner> ] ,]? <color-stop>[, <color-stop>]+) <side-or-corner> = [left | right] || [top | bottom]   八个方向,to bottom是默认值,相当于1