动态规划初步

Update 2019.8.23

• 又回来刷题了。。。。

---

• 最近发现小绿本（《算法竞赛入门经典——习题与解答》）上的题值得一做，题解都写得很清真，不会像某谷上的题解，有一些奇技淫巧，不看 $Code$ 的情况下一般都可以打出来，提高自己的代码实现能力。
• 然后我就先从动态规划开始吧 $qwq$ ~~

---

小紫书

例题：9-1

• 题目链接：[洛谷] [UVA]
• 分析：
  我觉得刘汝佳分析的思路写的很好，先抄下来：

  时间是单向流逝的，是一个天然的 ”序“ 。影响到决策的只有当前时间和所处车站，所以可以用 $d\left[i\right]\left[j\right]$ 表示时刻 $i$ ，你在车站 $j$ ，最少还需要多少等待时间。边界条件是 $d\left[T\right]\left[n\right]=0$ ，其他 $d\left[T\right]\left[j\right]=\infty (j\ne n)$ 。有 3 种决策：

  1. 等 1 分钟
  2. 做左边的车
  3. 做右边的车

  然后反着推就可以啦~
  思路好清晰鸭 qwq，我写题解完全不能达到的水平……
• $Code$：

第一次打的时候用的是 $Emacs$ ，然后我的配置文件有一点问题，然后编译以后代码就被吃了。。。。

劳资又 tm 打了一遍。。。。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85

#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> using namespace std; const int MAXN = 1e3 + 5; const int MAXT = 1e3 + 5; const int INF = (1 << 30); int n, m, t, dis[MAXN], f[MAXN][MAXT]; bool flag[MAXN][MAXT][2]; inline void Init () { memset (dis, 0, sizeof (dis)); memset (flag, false, sizeof (flag)); memset (f, 0, sizeof (f)); return; } int main() { int cnt = 0; while (true) { Init (); cnt ++; scanf ("%d", &n); if (n == 0) { break; } scanf ("%d", &t); for (int i = 1; i <= n - 1; i++) { scanf ("%d", &dis[i]); } scanf ("%d", &m); for (int i = 1; i <= m; i++) { int temp; scanf ("%d", &temp); for (int j = 1; j <= n; j++) { flag[j][temp][0] = true; temp += dis[j]; } } scanf ("%d", &m); for (int i = 1; i <= m; i++) { int temp; scanf ("%d", &temp); for (int j = n; j >= 1; j--) { flag[j][temp][1] = true; temp += dis[j - 1]; } } for (int i = 1; i <= n; i++) { f[i][t] = INF; } f[n][t] = 0; for (int i = t - 1; i >= 0; i--) { for (int j = 1; j <= n; j++) { f[j][i] = f[j][i + 1] + 1; if(j < n && flag[j][i][0] && i + dis[j] <= t) { f[j][i] = min (f[j][i], f[j + 1][i + dis[j]]); } if(j > 1 && flag[j][i][1] && i + dis[j - 1] <= t) { f[j][i] = min (f[j][i], f[j - 1][i + dis[j - 1]]); } } } printf ("Case Number %d: ", cnt); if (f[1][0] >= INF) { printf ("impossible\n"); } else printf ("%d\n", f[1][0]); } return 0; }

小绿书—《习题与解答》

1.最长的滑雪路径

• 题目链接：[洛谷]|[UVA（科学上网）]
• 分析：直接引书中的话：

  用 $D[i,j]$ 来表示从 $[i,j]$ 开始能走的高度严格递减的最长路，则很容易发现 $D[i,j]$ 的状态转移方程：

  $$D[i,j]=max\left(D\right[i_1,j_1]+1)$$

  其中 $(i_1,j_1)$ 是比 [i,j] 高度小的 4 个相邻的格子之一。边界条件是当没有符合条件的 $i_1$ 和 $j_1$ 时， $D[i,j]=1$。使用记忆化搜索即可，时间复杂度 $O(R\times C)$ 。

  另外值得注意的是，记得不要让搜索越界！我是多久没写过搜索了，因为这个东西我调了 20 分钟 QAQ​
• $Code$：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53

#include <iostream> #include <cstdio> #include <cstring> using namespace std; const int MAXRC = 1e2 + 5 ; const int cmp[4][2]={{1,0},{-1,0},{0,1},{0,-1}}; int T, r, c, ans ; int data[MAXRC][MAXRC],dp[MAXRC][MAXRC]; char ch[MAXRC]; inline void Init(){ ans=0; memset (data,0,sizeof (data)); memset (dp,0,sizeof (dp)); return; } void DP (int x,int y){ for (int i=0;i<4;i++){ int tox=x+cmp[i][0]; int toy=y+cmp[i][1]; if (tox<1||tox>r||toy<1||toy>c) continue; if (data[tox][toy]<data[x][y]){ if (!dp[tox][toy]){ dp[tox][toy]=1; DP(tox,toy); } dp[x][y]=max(dp[x][y],dp[tox][toy]+1); } } ans=max(ans,dp[x][y]); return; } int main() { scanf ("%d" ,&T); while (T--) { scanf ("%s", ch); printf ("%s: ", ch); Init(); scanf ("%d%d", &r, &c); for (int i=1;i<=r;i++) for (int j=1;j<=c;j++) scanf ("%d",&data[i][j]); for (int i=1;i<=r;i++){ for (int j=1;j<=c;j++){ if (dp[i][j]) continue; dp[i][j]=1; DP(i,j); } } printf ("%d\n",ans); } return 0; }

2.免费糖果

• 题目链接：[洛谷]|[UVA（科学上网）]
• 分析：用 $dp[a,b,c,d]$ 来表示 4 个队列的拿取情况所对应口袋中的糖数。枚举每一种情况，如果篮子里有这种糖果了，就把篮子相应的糖果 $-1$ ；反之， $+1$ 。可以使用记忆化搜索实现，这样可以去除大量重复情况。
• $Code$：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54

#include <iostream> #include <cstdio> #include <cstring> using namespace std; const int MAXN=45; int data[5][MAXN],n; int dp[MAXN][MAXN][MAXN][MAXN]; int top[5]; inline void Init(){ top[1]=top[2]=top[3]=top[4]=1; memset(dp,-1,sizeof (dp)); return; } int dfs (int cnt,bool flag[]){ int ans=0; int a=top[1]; int b=top[2]; int c=top[3]; int d=top[4]; if (dp[a][b][c][d]!=-1) return dp[a][b][c][d]; if (cnt==5) return dp[a][b][c][d]=0; for (int i=1;i<=4;i++){ if (top[i]>n) continue; int to=data[i][top[i]]; top[i]++; if (flag[to]){ flag[to]=false; ans=max(ans,dfs(cnt-1,flag)+1); flag[to]=true; } else { flag[to]=true; ans=max(ans,dfs(cnt+1,flag)); flag[to]=false; } top[i]--; } dp[a][b][c][d]=ans; return dp[a][b][c][d]; } int main(){ while (true){ scanf ("%d",&n); if (!n) return 0; Init(); bool flag[MAXN]; memset(flag,false,sizeof (flag)); for (int i=1;i<=n;i++) for (int j=1;j<=4;j++) scanf ("%d",&data[j][i]); printf ("%d\n",dfs(0,flag)); } return 0; }