来源:
http://acm.hust.edu.cn:8080/judge/contest/view.action?cid=10907#problem/A
ACM International Collegiate Programming Contest, Asia-Amritapuri Site, 2011
题意:有一个矩阵,要求从左上角走到右下角。每个方格里有正数或者负数。从左上角走的时候有一定的血量,走到一个方格,若该方格是负数,则需要减去该方格的血量,若是正数,则可以加上该方格的血量。若血量小于等于0,则不能继续走下去。求若想走到右下角,则从左上角出发时最少需要多少的血量。
思路:这道题我是用DP做的。不过标程是用二分做的。我的思路是:倒着DP。即从右下角向左上角Dp。到达右下角时的血量最少为1,另dp[i][j]为到达第i行第j列时能继续往下走的最少血量。则dp[i-1][j] = min(dp[i-1][j] , dp[i][j] - num[i-1][j]), dp[i][j-1] = min (dp[i][j-1], dp[i][j] - num[i][j-1])。这样一直求上去就可以得到dp[1][1]的值。在这个过程中,有一点需要注意,若求出的某点血量为小于等于0,则应该赋值为1,这点很好理解。最后dp[1][1] = min (dp[1][2] , dp[2][1])。
代码:
#include <iostream>#include <cstdio>#include <string.h>#include <climits>using namespace std;#define CLR(arr,val) memset(arr,val,sizeof(arr))const int N = 510;int dp[N][N],num[N][N];int min(int a,int b){ return a<b ? a:b;}int main(){ //freopen("1.txt","r",stdin); int row,col; int numcase; scanf("%d",&numcase); while(numcase--){ scanf("%d%d",&row,&col); CLR(num,0); for(int i = 1; i <= row; ++i){ for(int j = 1; j <= col; ++j){ scanf("%d",&num[i][j]); dp[i][j] = INT_MAX; } } dp[row][col] = 1; num[1][1] = 1; for(int i = row; i >= 1; --i){ for(int j = col; j >= 1; --j){ if(i-1 > 0 && i-1 < row){ int x = dp[i][j] - num[i-1][j]; if(x <= 0) x = 1; dp[i-1][j] = min(dp[i-1][j],x); } if(j-1 > 0 && j - 1 < col){ int x = dp[i][j] - num[i][j-1]; if(x <= 0) x = 1; dp[i][j-1] = min(dp[i][j-1],x); } } } int mm = INT_MAX; mm = min(mm,dp[1][2]); mm = min(mm,dp[2][1]); printf("%d\n",mm); } return 0;}
分享到:
相关推荐
MADRID
madrid.zip
Madrid2e
Madrid Metropolis Dataset 是用于三维建模的图片数据集,其利用平均极线几何求解运动问题中的 结构 。 该数据集由康奈尔大学于 2014 年发布,主要发布人为 Kyle Wilson 和 Noah Snavely,相关论文有《Robust ...
IonicMadrid:Charlas Ionic Madrid
Holandeses_en_Madrid:Página网站“ Holandeses en Madrid”
42madrid_Cub3D
语言:English Cantineoqueteveo-Concurso Seo Madrid 2019 市场营销协调委员会
42-madrid
predi_madrid
Castform-Madrid
Piscine-42-madrid:Piscine noviembre 2019,42马德里
Great Clarendon Street, Oxford 0X2 6DP Great Clarendon Street, Oxford 0x2 6dp Oxford University Press is a department of the University of Oxford. It furthers the University's objective of ...
数据集包含在2018年欧洲冠军联赛决赛中在皇家马德里和利物浦之间捕获的推文。 Tweets during Real Madrid vs Liverpool_datasets.txt Tweets during Real Madrid vs Liverpool_datasets.zip
GTFS马德里长凳我们介绍了GTFS-Madrid-Bench,这是一个评估声明式KG构建引擎的基准,该引擎可用于提供对(虚拟)知识图的访问机制。 我们的提案提出了几种方案,这些方案旨在衡量性能和可伸缩性以及所有这类引擎的...
这是关于西班牙马德里的一家交通服务公司的公共交通数据,可以用此数据来进行交通流预测,路径规划,路径导航方面的。
Qiskit Camp-Hackaton Madrid 2019-生命的量子游戏 此包含我们的项目:幻灯片和代码,用于 。 我们做了什么? 要将量子计算应用于: 首先尝试加速新细胞的产生 然后我们更新了规则,以纳入量子物理学 有关更多详细...