由于晚自习没来，这只是自己的看法。
有错请指出，谢谢。
给你一个长度为 n n n的区域，每一个单位长度的区域有一个价值vi，现在规定合并一个区域（例如：2 - 5，以前的分离点为4，价值分别为3 2 5 4）带来的价值为（合并后所在区间左右端点区域里金钥匙价值之和）（之前分离的时候所在区域的金钥匙价值），在例子中便是：（3 + 4） * 5 = 35.求出最大价值以及合并区域。
input7
1 2 3 4 5 6 7
238
1 2 3 4 5 6
首先，拿到这道题，我发现这道题本质是一个区间合并并且要求输出路径的题。很容易，联想到关于区间的知识——区间DP。
再转向数据范围：n ≤ 300，也就是说，时间复杂度在 O ( n 3 ) O(n^3) O(n3)以内，便不会超时。
好，开始做题。
首先，是一个输入。
#includeusing namespace std; const int N = 3e2 + 5; int n, a[N]; int main() { cin >> n; for (int i = 1;i <= n;i++) { cin >> a[i]; } return 0; }
接着，我们该实现求获得的最大价值了。
首先，几个步骤：
for 枚举长度 for 枚举左端点 求出右端点 for 枚举分割点 更新dp思考一：区间长度从几开始枚举
显然，题目让我们分割区间，将一个1 - n的区间，分割成1 - k和k + 1 - n两个区间，那么，一个区间无法分割，而两个区间可以分割成1-1和2-2.所以长度从2开始枚举。
思考二：枚举分割点的取值范围是多少题目让我们分割区间，将一个1 - n的区间，分割成1 - k和k + 1 - n两个区间，所以k 大于等于1，k + 1小于等于n。
思考三：如何求转移方程式论转移，无非就两种，选与不选。首先，是选，选的话，得到的价值就由三部分组成：左区间的价值，右区间的价值和分离所得的价值。不选，便是它本身。所以，最终的价值应该在选与不选中取最大值。
#includeusing namespace std; const int N = 3e2 + 5; int n, a[N], dp[N][N]; int main() { cin >> n; for (int i = 1;i <= n;i++) { cin >> a[i]; } for (int len = 2;len <= n;len++) { for (int i = 1;i <= n - len + 1;i++) { int j = i + len - 1; for (int k = i;k + 1 <= j;k++) { dp[i][j] = max(dp[i][j], dp[i][k] + dp[k + 1][j] + (a[i] + a[j]) * a[k]); } } } cout << dp[1][n] << endl; return 0; }
最后，我们来思考：如何求出合并的断点k。
由最长上升子序列得到的启发——开一个数组标记它是否被更新过。
也就是在第三重循环里，用if去判断。
#includeusing namespace std; const int N = 3e2 + 5; int n, a[N], dp[N][N], c[N][N]; int main() { cin >> n; for (int i = 1;i <= n;i++) { cin >> a[i]; } for (int len = 2;len <= n;len++) { for (int i = 1;i <= n - len + 1;i++) { int j = i + len - 1; for (int k = i;k < j;k++) { if (dp[i][j] < dp[i][k] + dp[k + 1][j] + (a[i] + a[j]) * a[k]) { c[i][j] = k; dp[i][j] = dp[i][k] + dp[k + 1][j] + (a[i] + a[j]) * a[k]; } } } } cout << dp[1][n] << endl; return 0; }
然后，做好了求出合并的断点k的前置工作，便开始想用dfs拉序列。
#includeusing namespace std; const int N = 3e2 + 5; int n, a[N], f[N][N], dp[N][N]; bool vis[N][N]; void check(int i, int j) { if (i == j) return; printf("%d ", f[i][j]); check(i, f[i][j]); check(f[i][j] + 1, j); } int main() { cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; } for (int len = 2; len <= n; len++) { for (int i = 1; i <= n - len + 1; i++) { int j = i + len - 1; for (int k = i; k < j; k++) { int t = dp[i][k] + dp[k + 1][j] + (a[i] + a[j]) * a[k]; if (dp[i][j] < t) { dp[i][j] = t; f[i][j] = k; } } } } cout << dp[1][n] << endl; check(1, n); return 0; }
但这样，你就只有20 points 。
在这里，注意题目的要求是
先打印
一分为二的区域，然后从左到右打印二分为四的分离区域，然后是四分为八的……
也就是说，我们遍历的类似于一个二叉树，要逐层遍历。
所以，应该这样。
#includeT2 颜色联通块 一、题目大意using namespace std; const int N = 3e2 + 5; int n, a[N], dp[N][N], c[N][N]; bool vis[N][N]; void dfs(int l, int r, int k) { if (k == 1) return; if (l == r) return; if (!vis[l][r]) { cout << c[l][r] << " "; vis[l][r] = 1; } dfs(l, c[l][r], k - 1), dfs(c[l][r] + 1, r, k - 1); } int main() { cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; } for (int len = 2; len <= n; len++) { for (int i = 1; i <= n - len + 1; i++) { int j = i + len - 1; for (int k = i; k < j; k++) { // dp[i][j] = max(dp[i][j], dp[i][k] + dp[k + 1][j] + (a[i] + a[j]) * a[k]); if (dp[i][j] < dp[i][k] + dp[k + 1][j] + (a[i] + a[j]) * a[k]) { c[i][j] = k; dp[i][j] = dp[i][k] + dp[k + 1][j] + (a[i] + a[j]) * a[k]; } } } } cout << dp[1][n] << endl; for (int i = 1; i <= n; i++) { dfs(1, n, i); } return 0; }
就是说，你有n个方块，每个方块有一个颜色，你可以进行这样的操作：将两个颜色分别相同的块合并为任意一种颜色，问要多少次操作才能将所有块变为一种颜色。
二、做题思路“两个颜色分别相同的块”说明这又是一个有关区间的题目——区间DP。而“合并”操作便可转移DP。
再看范围，1 <= N <= 5000，所以DP中不能枚举中间点。
首先，是输入。
#includeusing namespace std; const int N = 5e3 + 5; int n, a[N]; int main() { cin >> n; for (int i = 1;i <= n;i++) { cin >> a[i]; } return 0; }
但在这里，我们观察一下，若有颜色相同的在一起，一起改变，和看作一个块改变实际上是一样的，所以，我们输入时，可以优化。减小n的值。
#includeusing namespace std; const int N = 5e3 + 5; int n, a[N]; int main() { cin >> n; for (int i = 1;i <= n;i++) { cin >> a[i]; if (a[i] == a[i - 1]) i--, n--; } return 0; }
然后，我们来看DP。首先，一个十分普通的DP框架：
#includeusing namespace std; const int N = 5e3 + 5; int n, a[N], dp[N][N]; int main() { cin >> n; for (int i = 1;i <= n;i++) { cin >> a[i]; if (a[i] == a[i - 1]) i--, n--; } for (int len = 2;len <= n;len++) { for (int i = 1;i <= n - len + 1;i++) { int j = i + len - 1; } } cout << dp[1][n]; return 0; }
这个应该没问题。
首先，我们DP的状态是指在i - j的区间里，让这个区间变为一个颜色相同的块所用的操作次数。
分两种情况：
当a[i] == a[j]相等时，那么DP就应该由 dp[i + 1][j - 1] + 1转移，有人可能会说，如果是1 1 1这种情况呢？他就应该等于dp[i + 1][j - 1]呀，但是，请注意，这种情况是不存在的，因为我们在输入的时候进行了预处理，避免了这种情况。只可能是x y x的情况。
Two否则，因为我们是知道dp[i + 1][j]和dp[i[j - 1]的，而我们又只扩展i， j，所以一共有两种情况：dp[i + 1][j]和dp[i[j - 1]。因为a[i]和a[j]是不同的，所以，dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 1。
#includeT3 灯泡 一、题目大意using namespace std; const int N = 5e3 + 5; int n, a[N], dp[N][N]; int main() { cin >> n; for (int i = 1;i <= n;i++) { cin >> a[i]; if (a[i] == a[i - 1]) i--, n--; } for (int len = 2;len <= n;len++) { for (int i = 1;i <= n - len + 1;i++) { int j = i + len - 1; if (a[i] == a[j]) dp[i][j] = dp[i + 1][j - 1] + 1; else dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 1; } } cout << dp[1][n]; return 0; }
给出这样一幅图，和已知信息H、h和D的值，求出L（影子的长度）。
首先，我们要找出L与D、H和h的公式。于是我们可以利用相似三角形（戳我！）来计算。
最后，发现公式为：L = D - x + H - (H - h) / x * D
接着，我们可以带入几个值，发现，L他并非单调递增或单调递减，是一条曲线。我们要在这条曲线上寻找凸点。便可以想到三分。
#includeusing namespace std; int T; double H, D, h; double check(double x) { return D - x + H - (H - h) / x * D; } int main() { cin >> T; while (T--) { cin >> H >> h >> D; double l = ?, r = ?; while (r - l >= 1e-12) { double midl = l + (r - l) / 3.0, midr = r - (r - l) / 3.0; if (check(midl) > check(midr)) { r = midr; } else { l = midl; } } cout << fixed << setprecision(3) << check(l) << endl; } return 0; }
那么，“？”处，应该填什么呢？最大值无疑就是D，全部覆盖完，最小值便是(H - h) / H * D。
所以完整代码：
#includeusing namespace std; int T; double H, D, h; double check(double x) { return D - x + H - (H - h) / x * D; } int main() { cin >> T; while (T--) { cin >> H >> h >> D; double l = (H - h) / H * D, r = D; while (r - l >= 1e-12) { double midl = l + (r - l) / 3.0, midr = r - (r - l) / 3.0; if (check(midl) > check(midr)) { r = midr; } else { l = midl; } } cout << fixed << setprecision(3) << check(l) << endl; } return 0; }
