dp的刷表法和填表法

参考：

动态规划刷表法 - acmer_xue的博客 - CSDN博客
http://blog.csdn.net/qq_30241305/article/details/52198780

一.先简单讲下什么是填表法，什么是刷表法。

填表法 ：就是一般的动态规划，当前点的状态，可以直接用状态方程，根据之前点的状态推导出来。

刷表法：由当前点的状态，更新其他点的状态。需要注意：只用当每个状态所依赖的状态对它的影响相互独立。

二.通过例题看刷表

链接：http://exam.upc.edu.cn/problem.php?id=2383

题意：三个数，T表示最大的饱腹值，A表示吃a可以增加的饱腹值，B表示吃b可以增加的饱腹值。ab都有无穷多个。初始状态是0，可以有一次通过喝水，来使饱腹值减少一半（向下取整）的机会。

分析：首先按照一般的动态规划，会有问题。

为什么不能用填表法？

因为当前状态既与之前的状态有关，又与之后的状态有关。当前的状态与dp[ i - a],dp[i - b],dp[i * 2]有关。所以用刷表法，来直接更新状态。

此题中，喝水后的状态可以在喝水的基础上计算。及可以先计算所有喝水前的状态，再计算所有喝水后的状态。喝水前的状态可以更新喝水后的状态。

另：注意，本题中饱腹值不能超过最大值T

代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <sstream>
 5 #include <string>
 6 #include <algorithm>
 7 #include <list>
 8 #include <map>
 9 #include <vector>
10 #include <queue>
11 #include <stack>
12 #include <cmath>
13 #include <cstdlib>
14 using namespace std;
15 int dp[5000005][2];
16 int main()
17 {
18     //freopen("in.txt","r",stdin);
19     int p,a,b;
20     scanf("%d%d%d",&p,&a,&b);
21     dp[0][0] = dp[0][1] = 1;
22     for(int j = 0; j < 2; j ++)
23     {
24         for(int i = 0; i <= p; i ++)
25         {
26             if(dp[i][j])
27             {
28                 if(i+ a <= p)
29                     dp[i + a][j] = 1;
30                 if(i + b <= p)
31                     dp[i + b][j] = 1;
32                 if(j == 0)
33                     dp[i / 2][1] = 1;
34             }
35         }
36     }
37  
38  
39     int ans;
40     for(int i = p; i >= 0; i --)
41     {
42         if(dp[i][0] || dp[i][1])
43         {
44             ans = i;
45             break;
46         }
47     }
48     printf("%d
",ans);
49  
50     return 0;
51 }