【蓝桥杯】每日练习 Day19，20

目录

前言

蒙德里安的梦想

分析

最短Hamilton路径

分析

代码

乌龟棋

分析

代码

松散子序列

分析

代码

代码

---

前言

今天不讲数论（因为上课学数论真是太难了，只学了高斯消元）所以今天就不单独拿出来讲高斯消元了。今天讲一下昨天和今天做的四种题型（两个状压dp，两个线性dp），时间仓促，我们马上开始吧。

---

蒙德里安的梦想

---

分析

首先来分析一下暴力的时间复杂度，因为只有两种图形，所以我们只需要考虑一种图形的放法，随后在将另一种放进去即可，所以我们分析时间复杂度也只分析一种图形的放法，我们将两个相邻的方块看成一个整体，显然时间复杂度为：

考虑极限情况N = M = 11，结果是2^55左右，显然是超时的。所以暴力搜索不考虑。

我们注意到N和M都很小（这种一般就可以考虑能否使用状态压缩dp了，经验之谈），所以我们考虑状态压缩dp，用二进制枚举所有的选法。

因为我也不太能想出来这道题的解题思路是怎么来的，所以我这边就直接用答案套题目了。

我们枚举每一列的所有选法，状态总数就是

1 << n

我们设

m = 1 << n。

状态表示：dp[m][n] 枚举第n列使用m排列的所有选法。

状态转移：dp[m][n] += dp[s][n - 1]，当然这两个状态必须是能够同时存在并且合法的。

现在我们来分析一下什么样的状态算是合法的，因为我们枚举的是横着摆放的所有方法，所以就必须满足放完之后能够使用竖着摆放的方块填满整个矩形，显然要想满足这个条件这一列连续不放置的方块数量就必须是偶数（我们是用每一列来划分的，所以默认前面的所有列都是已经放满的，无需考虑复杂情况。）

随后我们再来思考一下怎样算是这一层与上一层的状态是共存的，显然不能重复放置。所以我们的划分就已经完成了。

时间复杂度分析：大概是1亿左右，可以通过。

/*数位dp，因为只有两种方块并且必须填满才算合法情况，所以我们只枚举一种的放法随后判断这种方法是否合法。第一列所有状态都是合法的。
*/
#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;
const int N = 15, M = 1 << N;
int n, m;
LL dp[M][N]; //第N列以M的摆放方式放置的所有方案
bool is_realy[M];
//LL l;
int main()
{while(scanf("%d%d", &n, &m) && n && m){//memset(is_realy, false, sizeof is_realy);for(int i = 0; i < 1 << n; i++) //枚举所有状态{int cnt = 0; //记录非0长度is_realy[i] = true;for(int j = 0; j < n; j++) //查看每一位{if((i >> j) & 1) //是1{if(cnt & 1) //奇数{is_realy[i] = false; //非法状态break;}cnt = 0;}elsecnt++;}if(cnt & 1) is_realy[i] = false;}memset(dp, 0, sizeof dp); //初始化for(int i = 0; i < 1 << n; i++) if(is_realy[i])dp[i][1] = 1;for(int i = 2; i <= m; i++) //枚举每一层 0， m - 1是合法层{for(int j = 0; j < 1 << n; j++) //枚举当前状态for(int k = 0; k < 1 << n; k++) //枚举上一层状态if((j & k) == 0 && is_realy[j | k])dp[j][i] += dp[k][i - 1];}printf("%lld\n", dp[0][m]);}
}

---

最短Hamilton路径

---

分析

哈密尔顿路问题，每个结点都要经过一次且仅一次。

看到这个最终状态其实就能够感觉出来是动态规划了，话不多说，我们来考虑状态压缩dp。

状态表示：dp[i][i]，表示以i结尾的包含i的路径的所有选法。

老规矩，分析上一个结点，所以我们枚举上一个结点。

状态转移：

dp[i][j] = min(dp[i][j], dp[i - 1 << j][k] + map[k][j])

时间复杂度分析：枚举路径数是2^n = 1e6，枚举每个结点和上一层结点是n * n，所以最终的时间复杂度就是，大概是4亿左右，这道题时间限制是5s可以通过。

---

代码

// Hamilton路径——经过所有点一次且仅一次的路径
// dp[M][N] 从1出发，以n结尾的所有路径的最短值。
#include<iostream>
#include<cstring>
using namespace std;
const int N = 21, M = 1 << N;
int n;
int map[N][N];
int dp[M][N];
​
int main()
{scanf("%d", &n);for(int i = 0; i < n; i++)for(int j = 0; j < n; j++)scanf("%d", map[i] + j);// 枚举所有路径memset(dp, 0x3f, sizeof dp);dp[1][0] = 0;for(int i = 0; i < 1 << n; i++) //枚举所有路径{for(int j = 0; j < n; j++) //枚举以哪个点结尾{if(i >> j & 1) // 路径中包含i,枚举上一个点结尾for(int k = 0; k < n; k++){if(i >> k & 1) //也在路径中dp[i][j] = min(dp[i][j], dp[i - (1 << j)][k] + map[k][j]);}}}printf("%d", dp[(1 << n) - 1][n - 1]);
}

---

乌龟棋

---

分析

本来以为是背包但是发现结果与选的个数无关只与顺序有关并且是一定可以选完的，所以排除掉背包。

发现题目中强调了只有四种跳跃幅度，所以从这里入手，如何来表示状态呢？

欸？有一种“非常暴力”的表示方法——dp[N][M][M][M][M]，显然这个状态数量有点多了，大概是350 * 41 * 41 * 41 * 41 = 8.9亿，严重超时，超空间。

随后我们来分析一下能不能优化呢？可以发现N和每一个M彼此之间都是有关联的，只需要知道其余4个就可以求出第5个，所以我们可以将状态优化到4维，因为N最大，所以我们优先考虑优化掉N，状态就变为了：dp[M][M][M][M]，大概数41 * 41 * 41 * 41 = 2560000空间上大概是9M，可以通过。

状态表示有了接下来我们就来思考一下状态计算。

显然dp[a][b][c][d] = max(dp[a - 1][b][c][d], dp[a][b - 1][c][d], dp[a][b][c - 1][d], dp[a][b][c][d - 1]) + s。

---

代码

/*01背包? 对于每个位置，枚举使用哪张卡片到达？ 会出现重复吧。。。学到了新的思路，每个卡片都存储一下选择了多少张，这样就不会出现重复的了还能保证没有先后顺序的随机查找
*/
#include<iostream>
using namespace std;
const int N = 360, M = 42;
int n, m;
int a[N], s[5];
int dp[M][M][M][M]; //四维状态存储每种卡片的使用情况
int main()
{scanf("%d%d", &n, &m);for(int i = 1; i <= n; i++)scanf("%d", &a[i]);for(int i = 1; i <= m; i++){int x; scanf("%d", &x);s[x]++; }//dp[0][0][0][0] = a[1];for(int A = 0; A <= s[1]; A++)for(int B = 0; B <= s[2]; B++)for(int C = 0; C <= s[3]; C++)for(int D = 0; D <= s[4]; D++){if(A) dp[A][B][C][D] = max(dp[A][B][C][D], dp[A - 1][B][C][D]); if(B) dp[A][B][C][D] = max(dp[A][B][C][D], dp[A][B - 1][C][D]); if(C) dp[A][B][C][D] = max(dp[A][B][C][D], dp[A][B][C - 1][D]); if(D) dp[A][B][C][D] = max(dp[A][B][C][D], dp[A][B][C][D - 1]); dp[A][B][C][D] += a[1 + A + 2 * B + 3 * C + 4 * D];}printf("%d", dp[s[1]][s[2]][s[3]][s[4]]);return 0;
}

---

松散子序列

---

分析

题目要求就是找出acsii相加并且每个字符在原串中的距离要大于1的所有子序列的最大值（语文题）。

这道题很简单，主播给大家提供两种思路。

第一种，以子序列的最后一个结点划分，运用最长上升子序列的思想，然每次更新最大值即可。（这也是我认为最简单的思路）。

状态表示：dp[i]表示以第i个字符结尾的子序列的最大值。

状态转移：dp[i] = max(dp[i - 2], dp[i - 3], ...) + str[i]，因为我们求的是线性值，所以可以使用贪心优化，每次只拿最大值判断即可。

---

代码

#include<iostream>
using namespace std;
const int N = 1000010;
int mxx;
int dp[N];
int n;
char str[N];
​
int main()
{scanf("%s", str + 1);for(int i = 1; str[i]; n = i++){dp[i] = mxx + str[i] - 'a' + 1; //记录最大值mxx = max(mxx, dp[i - 1]);}printf("%d", max(dp[n], dp[n - 1]));return 0;
}

第二种呢，是使用状态机dp，显然每个字符只有两种状态——选或不选，随后运用背包的思想表示出状态即可。

状态表示：dp[i][2]表示第i个字符选或不选。

状态转移：dp[i][0] = max(dp[i - 1][0], dp[i - 1][1])，dp[i][1] = dp[i - 1][0] + s[i]。

---

代码

#include<iostream>
using namespace std;
const int N = 1000010;
int dp[N][2];
int n;
char str[N];
​
int main()
{scanf("%s", str + 1);for(int i = 1; str[i]; n = i++){dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);dp[i][1] = dp[i - 1][0] + str[i] - 'a' + 1;}printf("%d", max(dp[n][0], dp[n][1]));return 0;
}

对于这个状态呢，我们可以将其优化到一维——dp[i]存储选或不选的最大值（类似背包）。

状态表示：dp[i] = max(dp[i - 1], dp[i - 2]) + str[i]，前面是不选的最值，后面是选的最值。

#include<iostream>
using namespace std;
const int N = 1000010;
int dp[N];
int n;
char str[N];
​
int main()
{scanf("%s", str + 1);for(int i = 1; str[i]; n = i++)dp[i] = max(dp[i - 1], dp[i - 2] + str[i] - 'a' + 1);printf("%d", dp[n]);return 0;
}