首页 > 代码库 > poj3616题（动态规划），看了别人的提示，自己又写了一遍

poj3616题（动态规划），看了别人的提示，自己又写了一遍

2024-07-13 17:39:55   217人阅读

http://blog.csdn.net/xiaozhuaixifu/article/details/10818657参考文档链接

动态规划的主要三种思维方式：递推（从前往后想），状态转移（从后往前想），记忆化搜索（记录之后直接查寻）。这里使用状态转移的思维解题，明确除了没有移动这种情况，每次接受到或接受不到的位置可以由移位或不移位两种情况转移而来，到了该位置后根据原始数据直接加或不加总和。

#include <stdio.h>#include <stdlib.h>#include <algorithm>using namespace std;const int Max_T = 1001;const int Max_W = 31;int dp[Max_T][Max_W];int num[2][Max_T];int T, W;int main(){        memset(num, 0, sizeof(num));        memset(dp, 0, sizeof(dp));        while(scanf("%d %d", &T, &W) != EOF) {                for(int i = 1; i <= T; i ++) {                        int tmp;                        scanf("%d", &tmp);                        num[tmp == 2][i] = 1;//记录哪棵树上有苹果                }                for(int i = 1; i <= T; i++) {//初始状态即为只有一个苹果的状况                        for(int j = 0; j <= W && j <= i; j++) {                                if(j == 0)                                        dp[i][j] = dp[i - 1][j] + num[0][i];//没有移动则直接加第一棵树的苹果                                else                                        dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + num[j & 1][i];//根据是否转移得到现在的状态                        }                }                printf("%d\n", dp[T][W]);        }        return 0;}


联系
我们