首页 > 代码库 > 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免费馅饼(记忆化搜索)