首页 > 代码库 > hdu1876（dp）
hdu1876（dp）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1876
题意：问机器人到达终点的过程中最多有几次完全消耗完能量，消耗完这么多次能量的方式有几种。
分析：模拟一下可知，每次走到下一次消耗完时必定在一条对角线上。
以sample为例：
由于整个过程是以对角线的方向递推下去的，每次必定是往右下方走的，所以只需按着整常循环递推即可，当然按对角线右下方循环也可，不过那样略微麻烦。dp[i][j].num表示走到点（i，j）时消最多次耗完能量的次数，dp[i][j].cnt表示走到点（i，j）时消最多次耗完能量的方式。
状态转移方程为：
if(dp[x][y].num<dp[i][j].num+1)
{
dp[x][y].num=dp[i][j].num+1;
dp[x][y].cnt=dp[i][j].cnt;
}
else if(dp[x][y].num==dp[i][j].num+1)
dp[x][y].cnt+=dp[i][j].cnt;
本题还有好几个坑，能量为0的格子不能走，在终点时就不用递推了，样例没有刚好在终点时消耗完能量，所以这里被坑得好惨T^^T
#include <cstdio>#include <cstring>#include <cmath>#include <iostream>#include <algorithm>#include <queue>#include <cstdlib>#include <vector>#include <set>#include <map>#define LL long long#define mod 1000000007#define inf 0x3f3f3f3f#define N 10010using namespace std;struct node{ int cnt,num;} dp[110][110];int flag[110][110],a[110][110];int main(){ int t,n,m,x,y; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); for(int i=1; i<=n; i++) for(int j=1; j<=m; j++)scanf("%d",&a[i][j]); memset(flag,0,sizeof(flag)); memset(dp,0,sizeof(dp)); flag[1][1]=1; dp[1][1].cnt=1; for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) { if(i==n&&j==m)continue;//这里尤为注意 if(flag[i][j]) { if(!a[i][j])continue;//能量为0时不能走 x=i+a[i][j]; y=j; int t=a[i][j]+1; if(x+y<=m+n) { while(t--) { if(x>n||y>m||x<=0||y<=0)//不在方格内不算 { x--; y++; continue; } flag[x][y]=1; if(dp[x][y].num<dp[i][j].num+1)//取次数多的 { dp[x][y].num=dp[i][j].num+1; dp[x][y].cnt=dp[i][j].cnt; } else if(dp[x][y].num==dp[i][j].num+1) dp[x][y].cnt+=dp[i][j].cnt; x--; y++; } } else//走到终点没消耗完能量的 { if(dp[n][m].num<dp[i][j].num) { dp[n][m].num=dp[i][j].num; dp[n][m].cnt=dp[i][j].cnt; } else if(dp[n][m].num==dp[i][j].num) dp[n][m].cnt+=dp[i][j].cnt; } } } printf("%d %d\n",dp[n][m].num,dp[n][m].cnt); }}
hdu1876（dp）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。