首页 > 代码库 > hdu1176免费馅饼
hdu1176免费馅饼
先看题：http://acm.hdu.edu.cn/showproblem.php?pid=1176
这道题的状态转移方程不难找到dp[i][j] += max(dp[i + 1][j + 1],dp[i-1][j+1],dp[i][j+1]) 表示在第j秒的时候在i这个位置能接到的馅饼数 可是有两个特殊位置 0和10，这两个位置的状态转移方程需要另写dp[0][j] += max(dp[0][j+1],dp[1][i+1]) dp[10][j] += max(dp[10][j+1],dp[9][i+1]);
但是需要注意的是我们这个递推一定要从时间的最后开始推 不然也没法推 下面看代码
#include<iostream>#include <algorithm>#include<stdio.h>#include<string.h>using namespace std;int dp[11][100001];inline int Max(int a, int b, int c=-1) //这个函数很有意思 可以求两个数中最大的也可以求三个数最大的 可以研究研究{ if(a < b) a = b; if(a < c) a = c; return a;}int main(){ int n, i, j; int t, x; while (~scanf("%d", &n)&& n) { memset(dp, 0, sizeof(dp)); int MaxTime = 0; for (i=0; i<n; i++) { scanf("%d%d", &x, &t); dp[x][t]++; MaxTime = t>MaxTime ? t:MaxTime; //求最大时间是多少 } for (j=MaxTime-1; j>=0; j--) //j一定为最大时间-1 { dp[0][j] += Max(dp[0][j+1], dp[1][j+1]); dp[10][j] += Max(dp[10][j+1], dp[9][j+1]); for (i=1; i<10; i++) { dp[i][j] += Max(dp[i][j+1], dp[i+1][j+1], dp[i-1][j+1]); } } printf("%d\n", dp[5][0]); //输出5这个位置0秒时就行了 } return 0;}
hdu1176免费馅饼
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。