南华大学20级ACM队进阶动态规划练习解题报告1.石子合并(区间DP)题目链接：Acwing 石子合并题目分析：最后合并的石子堆的最优解可以分解为求合并前两堆石子的最优解，母问题可以被分解为子问题解决，因此可以选择DP解决//#pragma GCC optimize(2)#include<io...

题目链接：https://ac.nowcoder.com/acm/contest/82/B#include<bits/stdc++.h>#define LL long longusing namespace std; LL a[1000005], s[1000005]={0}, f[10...

题目传送门Problem DescriptionLong long ago, there lived two rabbits Tom and Jerry in the forest. On a sunny afternoon, they planned to play a game with so...

https://www.luogu.org/problemnew/show/P1063题解这个和合并石子的不同之处就是一个珠子多了头和尾的能量，并可以成环，成环的解决方法便是复制一遍即可，合并的时候就要有一些细节处理。比较简单的方法就是把长度为3的区间当成是两个珠子合并的结果，那么n个珠子合并便是长...

密码脱落题目链接 X星球的考古学家发现了一批古代留下来的密码。 这些密码是由A、B、C、D 四种植物的种子串成的序列。 仔细分析发现，这些密码串当初应该是前后对称的（也就是我们说的镜像串）。 由于年代久远，其中许多种子脱落了，因而可能会失去镜像的特征。 你的任务是： 给定一个现在看到的密码串，计算一...

[NOIP2007] 矩阵取数游戏题目链接思路：区间dp+高精发现每行答案分别独立，于是考虑分行做区间dp，最终把每行的答案相加。状态转移方程（对每一行，l为区间长度）：f[i][j]=max⁡(f[i+1][j]+a[i+1]∗2m−l−1,f[i][j−1]+a[j−1]∗2m−l−1)f[i][j]=\max(f[i+1][j]+a[i+1]*2^{m-l-1},~f[i][j-1]+a[j-1]*2^{m-l-1})f[i][j]=max(f[i+1][j]+a[i+1]∗2

https://vjudge.net/problem/CodeForces-607B题目大意：给出数组aaa，每次操作可以从aaa中选取一段回文串删去，问最少需要几次操作可以删去所有的元素。思路：区间dpdpdp，dp[i][j]dp[i][j]dp[i][j]表示删去区间[i,j][i,j][i,...

Time limit1000 ms Memory limit65536 kB The multiplication puzzle is played with a row of cards, each containing a single positive integer. During the ...

Description Sue和Sandy最近迷上了一个电脑游戏，这个游戏的故事发在美丽神秘并且充满刺激的大海上，Sue有一支轻便小巧的小船。然而，Sue的目标并不是当一个海盗，而是要收集空中漂浮的彩蛋，Sue有一个秘密武器，只要她将小船划到一个彩蛋的正下方，然后使用秘密武器便可以在瞬间收集到这个彩 ...

Description 一次考试共有n个人参加，第i个人说：“有ai个人分数比我高，bi个人分数比我低。”问最少有几个人没有说真话(可能有相同的分数) Input 第一行一个整数n，接下来n行每行两个整数，第i+1行的两个整数分别代表ai、bi 第一行一个整数n，接下来n行每行两个整数，第i+1行的 ...

You Are the One Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 32768/32768 K (Java/O

题意 "题目链接" Sol 神仙题Orz 考虑区间dp，如果我们只设$f[l][r]$表示$s_{lr}$被压缩的最小长度，而不去关心内部$M$分布的话，可能在转移的时候转移出非法状态 因此考虑多加一维表示当前子串中有没有$M$(默认第一个字符为$M$不统计在内) 转移的时候就考虑不同的$M$对当前 ...

题意 "题目链接" Sol 震惊，某知名竞赛网站竟照搬省选原题！ 裸的区间dp，$f[l][r]$表示干掉$[l, r]$的最小花费，昨天写的时候比较困于是就把能想到的转移都写了。。 cppp // luogu judger enable o2 // luogu judger enable o2 i ...

题意 "题目链接" Sol 裸的区间dp。 转移的时候枚举一下断点。然后判断一下区间内的字符串是否循环即可 cpp include define Pair pair define MP(x, y) make_pair(x, y) define fi first define se second de ...

做了许多动态规划题目，结合yxc大大的视频，总结了一点动态规划模板，用几道经典例题加以解释dp 第一步——状态表示（dp[i][]j）； 个人感觉一道动态规划题最难的一步就是状态表示，有一个清晰直观的状态表示做题时便势如破竹。状态标识包括集合和属性两点，集合是题目中的各个要素结合所形成的状态，属性则...

设一个 n 个节点的二叉树 tree 的中序遍历为（1,2,3,…,n），其中数字 1,2,3,…,n 为节点编号。每个节点都有一个分数（均为正整数），记第 i 个节点的分数为 di，tree 及它的每个子树都有一个加分，任一棵子树 subtree（也包含 tree 本身）的加分计算方法如下：sub...

N = int(input())arr = list(map(int, input().split()))from functools import lru_cache# dp(i, j) 表示所有中序序列是arr[i:j+1]的二叉树的价值的最大值以及最大值对应的树的根节点# 为了让前序序列的字典...

加分二叉树题目传送门题目描述设一个n个节点的二叉树tree的中序遍历为（1,2,3,…,n），其中数字1,2,3,…,n为节点编号。每个节点都有一个分数（均为正整数），记第i个节点的分数为di，tree及它的每个子树都有一个加分，任一棵子树subtree（也包含tree本身）的加分计算方法如下：su...

题目链接设一个n个节点的二叉树tree的中序遍历为（1,2,3,…,n），其中数字1,2,3,…,n为节点编号。每个节点都有一个分数（均为正整数），记第i个节点的分数为di，tree及它的每个子树都有一个加分，任一棵子树subtree（也包含tree本身）的加分计算方法如下：subtree的左子树的...