首页 > 代码库 > hdu 1176免费馅饼(记忆化搜索)
hdu 1176免费馅饼(记忆化搜索)
题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=1176
题意不解释了
简单的记忆化搜索可以拿来练练手,注意要从pos = 5 开始搜索
#include <iostream>#include <cstring>#include <algorithm>#include <cstdio>#include <cmath>using namespace std;const int M = 1e5 + 10;int dp[15][M] , t2[M][12];int dfs(int pos , int count) { if(count == 0) { if(pos == 6) { return 0; } else { return -1; } } if(dp[pos][count] != -1) return dp[pos][count]; int sum = 0; if(pos == 1) { sum += max(dfs(pos + 1 , count - 1) , dfs(pos , count - 1)); } else if(pos == 11) { sum += max(dfs(pos - 1 , count - 1) , dfs(pos , count - 1)); } else { sum += max(max(dfs(pos - 1 , count - 1) , dfs(pos + 1 , count - 1)) , dfs(pos , count - 1)); } if(sum != -1) { sum += t2[count][pos]; dp[pos][count] = sum; } return sum;}int main() { int n; while(scanf("%d" , &n) != EOF) { if(n == 0) break; memset(t2 , 0 , sizeof(t2)); int T = 0; for(int i = 0 ; i < n ; i++) { int x , y; scanf("%d%d" , &x , &y); t2[y][x + 1]++; T = max(T , y); } memset(dp , -1 , sizeof(dp)); int MAX = 0; for(int i = 1 ; i <= 11 ; i++) { MAX = max(MAX , dfs(i , T)); } printf("%d\n" , MAX); } return 0;}
hdu 1176免费馅饼(记忆化搜索)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。