祝馀宫

题面大秦 为你打开 题目传送门 题目翻译：有 $n$ 个地方（标号 $1$ 到 $n$ ）要从标号为 $0$ 的地方出去，经过所有的地方之后回来，求最短的时间，输入 $(n+1)$ 的矩阵 $a$，$a[i][j]$表示顶点 $i$ 到顶点 $j$ 所需要的时间。 第一行输入一个整数 $n(1≤n≤10)$ 。 接下来 $𝑛+1$ 行，每行 $n+1$ 个整数，表示矩阵中的元素，矩阵中的元素在区间 $[1,1000]$ 内。 思路这道题我们要同时兼顾经过了哪些点（因为要经过所有点），所以最好的方式就是把经过的点存下来，但是想要在递推过程中记录这些东西，有点困难。发现数据范围只有 $10$ 不难想到状压DP。因为状压DP是基于集合的DP，每经过一个点，就在状态中标记。 另外要处理某两个点之间的最短路，因为只有 $10$ 的数据范围，所以这个可以用 floyd 水水过。 此外，在标记每一个点的是否经过，还有一个很重要的元素是最后一个点是哪里。就比如说： 121 4 3 2 1 2 3 4 同样是经过了点 1 2 3 4 但是顺序不一样，路程就可能有变化，另外我们要从最后一个经过的点往 ...

题面大秦 为你打开 题目传送门 看不了的就看下面罢 从一个 $n\times n$ 的矩阵中选出一个元素之和最大的非空子矩阵。 思路思考一下，我们发现学过和这个最最有关的知识点应该是 “最大子段和” 。那么对于这道题的最大子矩阵应该怎么办呢？我们可以先参考一下最大子段和的代码。其主要思想就是能选就选，选不了就重开。 那么现在的问题是是否可以把最大子段和的思路借鉴到最大子矩阵中。矩阵本质上是一堆子段叠在一起得出的，且这些子段长度相等，一一对齐，才构造出了矩阵。我们将矩阵从上往下数的第一个子段称为第一行，那么一下所有字段的位置都是确定的了。那么我们就可以更具这个性质压缩一个矩阵。详见下图： 按照这个方法，我们把这个矩阵的第一行确定（假设是 $i$ ）后，假设当前矩阵是 $k$ 行，那么就把给出的矩阵中的第 $i$ 至 $i + k -1 $ 行拿出来压缩。然后对于压缩出来的东西求最大子段和就可以了 我们设 $dp[i]$ 表示宽度（每一行的长度）为 $i$ 的最大子矩阵，答案就从所有里面最大的找。详见代码。 代码12345678910111213141516171819202122232 ...

题面大秦 为你打开 题目传送门 题目翻译： 有 $n$ 种面值的硬币，面值分别为 $a_1,a_2,…,a_n$ ，数量分别为 $c_1,c_2,c_3,…,c_n$ ，请问在这些硬币的组合下，能够组成多少种不超过 $m$ 的面值。 思路显而易见的，这是一道多重背包模板题。面值是体积，数量就是每一种物品数量，$n$ 是物品个数。 但是这里的题目是 “能够组成多少种不超过 $m$ 的面值 ”，所以设定如下状态： 12dp[i]// 表示是否可以组成面值为 i 的方案 往下就是正常步骤了，详见代码。 代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748#include<bits/stdc++.h>using namespace std;int n, m;int a[110];int c[110];int top;int v[100010];int dp[100010];void Input() { scanf("%d%d&quo ...

题面大秦为你打开题目传送门 题目描述两人轮流从两堆牌中抽取最顶端或者最底部的牌，得到的分数加到自己身上，假设两个人都绝顶聪明，两个人都想让自己的得分最大，问先拿牌的最多能得多少分。 题解首先拿到这道题，要考虑怎么设置状态。 首先，想要记录当前排队状态，因为 $n$ 特别小，所以只需要直接开 $dp[l1][r1][l2][r2]$ 分别表示两个数组被取成这样的方案就可以了。但是还有一个问题就是要不要分开讨论两个人。 显然不用，因为题目给出要求 “假设两个人都绝顶聪明” 所以每个人都走最优方案就可以了。 代码12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849#include<bits/stdc++.h>using namespace std;int n;int a[25], b[25];int sum;int dp[25][25][25][25];void Input() { scanf("%d", &n ...