首页 > 代码库 > hdu1078 dp(递推)+搜索
hdu1078 dp(递推)+搜索
题目链接:http://acm.split.hdu.edu.cn/showproblem.php?pid=1078
题意:老鼠从(1.1)点出发,每次最多只能走K步,而且下一步走的位置的值必须必当前值大。求这些位置和的最大值。
思路:用搜索逐步找每个点能到达的最大值,也是子最优解到整体的最优解,dp思想。
下面AC代码:
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> using namespace std; int to[4][2]= {{1,0},{-1,0},{0,-1},{0,1}}; int n,k; int mp[105][105]; int dp[105][105]; int dfs(int x,int y) { int maxx=0,ans; if(dp[x][y]==0) { for(int i=1; i<=k; i++) { for(int j=0; j<4; j++) { int xx=x+to[j][0]*i; int yy=y+to[j][1]*i; if(xx>=1 && xx<=n && yy>=1 && yy<=n && mp[xx][yy]>mp[x][y]) { ans=dfs(xx,yy); maxx=max(maxx,ans); } } } dp[x][y]=mp[x][y]+maxx; } return dp[x][y]; } int main() { while(scanf("%d%d",&n,&k)==2) { if(n==-1 && k==-1) break; for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) scanf("%d",&mp[i][j]); memset(dp,0,sizeof(dp)); printf("%d\n",dfs(1,1)); } return 0; }
hdu1078 dp(递推)+搜索
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。