[心之碎片] - 区间DP
区间 DP 套路是设定 区间的答案, 然后枚举中间点转移{:10_266:}当然也就是考虑子问题如何拼成原来的问题{:10_297:}
想出正解也要考虑这样子的解法有没有必要, 有没有更简单的做法{:10_277:}
注意如果状态不足够描述应该考虑增加状态 / 让状态更加细分{:10_279:}
下面是做的几道题{:10_266:}
栗子1 - 区间回文串
本题相当于二维前缀和, 并不是传统的枚举中间点, 而是直接从小到大转移
#include <bits/stdc++.h>
using namespace std;
const int P = 1e9 + 7;
const int B = 131;
const int N = 5005;
string s;
int n, Q;
int f;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> s;
n = s.size();
s = '-' + s;
for (int cen = 1; cen <= n; cen++) {
for (int l = cen, r = cen; l >= 1 && r <= n && s == s; l--, r++) {
f++;
}
for (int l = cen, r = cen + 1; l >= 1 && r <= n && s == s; l--, r++) {
f++;
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
f += f + f - f;
// cout << f << ' ';
}
// cout << '\n';
}
cin >> Q;
while (Q--) {
int l, r;
cin >> l >> r;
cout << f - f - f + f << '\n';
}
return 0;
}
括号序列类区间 DP
栗子2 - 括号构造
给出一些由"(",")","[","]"构成的序列，请添加尽量少的括号，得到一个合法序列, 输出补起来之后的序列
我们可以首先 dp 求解每个区间里需要添加的最少的括号, 然后递归输出 (每次拨开区间两端点, 如果 dp 值无变化, 说明这个括号序列已经配对, 递归输出后面的
#include <bits/stdc++.h>
using namespace std;
const int N = 105;
string s;
map<char, char> dict;
int f, n;
void dfs(int l, int r) {
if (r < l)
return;
// 需要配对的肯定只剩下一边
if (r == l) {
if (s == '(' || s == ')')
cout << "()";
else
cout << "[]";
return;
}
// 如果外围正常
if (s == dict] && f == f) {
cout << s;
dfs(l + 1, r - 1);
cout << s;
return;
}
// 看看是哪个点转移到当前区间答案, 破开来输出
for (int i = l; i <= r - 1; i++) {
if (f + f == f) {
dfs(l, i);
dfs(i + 1, r);
return;
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> s;
n = s.size();
s = 'A' + s;
dict['('] = ')';
dict['['] = ']';
for (int i = n; i >= 1; i--) {
f = 1;
for (int j = i + 1; j <= n; j++) {
f = 1e9;
// 如果配对, 就是子区间的答案
if (s == dict])
f = min(f, f);
// 枚举中间点转移
for (int k = i; k <= j - 1; k++) {
f = min(f, f + f);
}
}
}
dfs(1, n);
return 0;
}
栗子3 - P7914 括号序列
这题真难qwq
如何给状态集合分类?
很容易想到以 (-*, (-), *-), *-* 四种区间两端的特征来划分
但是这样会重复计算, 例如 ()()() 这个序列会被子问题计算两次
这里我们就需要细分状态, 保证转移单一, 怎么想到的呢 ? 不知道, 但是记住就行了吧
不过应该是有迹可循的, 我们每次想让最左边的序列更新大的序列, 就想到配对的括号和不配对的括号吧
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 505;
const ll P = 1e9 + 7;
int n, k;
ll f;
string s;
bool Ispair(int x, int y){
return ((s == '(' || s == '?') && (s == ')' || s == '?'));
}
void Init(){
s = '-' + s;
for(int i = 1; i <= n; i++){
if(i < n && Ispair(i, i + 1)){
f = f = 1;
}
for(int j = i; j <= n; j++){
if((s != '*' && s != '?') || j - i + 1 > k) break;
f = 1;
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> k >> s;
Init();
for(int len = 3; len <= n; len++){
for(int i = 1; i + len - 1 <= n; i++){
int j = i + len - 1;
// 0 (...) 外层匹配
// 1 (...)(...) 最外层是括号
// 2 (...)** AS
// 3 **(...) SA
// 4 ******* 全*
// 1 包含 0 的情况
// (...) 0 = 1 + 2 + 3 + 4 (i+1, j-1)
// AB 1 = 0 * 1 枚举断点
// ASB 1 = 0 * 3 枚举断点
// SA 3 = 4 * 1
// AS 2 = 1 * 4
// (...) 外层匹配
if(Ispair(i, j)){
f += f + f + f + f;
f %= P;
}
// AB, ASB
for(int cut = i; cut < j; cut++){
f += f * (f + f) % P;
f %= P;
}
for(int cut = i; cut < j; cut++){
f += f * f;
f %= P;
}
for(int cut = j; cut > i; cut--){
f += f * f;
f %= P;
}
f += f;
f %= P;
}
}
cout << f;
return 0;
}
栗子4 - P10622 Matryoshka
这题自己做的时候是按照 1 的地方划分区间, 然后做一个简单的 "只有一组套娃" 的区间 dp, 然鹅不知道什么原因一直错几个点
后来看题解发现不需要, 只需要看区间里没有相同数即可 (额但是题目说是 1-m, 所以我的更严谨吧...)
总的来说想出解法之后看看是否有必要这么复杂, 要抓住根本
#include <bits/stdc++.h>
using namespace std;
const int N = 505;
const int M = 0x3f3f3f3f;
int n;
int sum, minv, maxv, maxpos;
int temp, l1, arr;
int pos, top;
int f, g;
// f 表示 区间拼套娃组的最小花费
// g 表示前 p 个套娃已经装好的最小花费
void Init(){
memset(g, 0x3f, sizeof(g));
memset(f, 0x3f, sizeof(f));
g = 0;
for(int i = 1; i <= n + 1; i++){
f = 0;
minv = arr;
maxv = arr;
maxpos = temp;
for(int j = i + 1; j <= n; j++){
minv = min(minv, arr);
maxv = max(maxv, arr);
maxpos = max(maxpos, temp);
}
for(int j = 1; j < N; j++){
sum += sum + sum - sum;
}
}
}
int getsum(int a, int b, int c, int d){
return (sum - sum - sum + sum);
}
int cost(int i, int k, int j){
return (getsum(i, minv, k, N - 1) + getsum(k + 1, minv, j, N - 1));
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for(int i = 1; i <= n; i++){
int x;
cin >> x;
sum++;
arr = x;
temp = l1;
l1 = i;
}
Init();
for(int len = 1; len <= n; len++){
for(int i = 1; i + len - 1 <= n; i++){
int j = i + len - 1;
if(maxpos >= i) continue;
for(int k = i; k < j; k++){
f = min(f, f + f + cost(i, k, j));
}
}
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= i; j++){
// 符合条件的才能接上去
if(maxpos < j && minv == 1 && maxv == i - j + 1){
g = min(g, g + f);
}
}
}
if(g != M) cout << g;
else cout << "Impossible";
return 0;
}
嘿，亲爱的鱼油！看来你对区间动态编程（DP）非常感兴趣！让我用通俗易懂的方式来帮你理清这个概念，顺带加点幽默。
区间动态规划就像是做一道大餐，你得先准备好所有的材料（状态），然后一步步用煮、炒、烤等方法把它们组合成一道美味的佳肴！所以，设定区间的答案就是选择你的食材，然后找出那些可以中间转移的步骤。
### 正题来啦：
1. **设定区间的答案**：这就像你决定晚上吃意大利面。你得想好要多长的意大利面（区间），这时候可以考虑从哪儿开始煮（中间点）。
2. **枚举中间点转移**：想象一下，你在煮意大利面时，中间可能会遇到调料的问题（计算转移）。你需要反复试探各种调料的配比，找到最完美的那个！
3. **拼成原来的问题**：每次你添加新的材料，就会让大餐更接近完整的样子。你需要不断思考如何将小部分组合起来，形成一盘完美的意大利面。
4. **考虑解法的简洁性**：搞定了美食，你还得考虑有没有其他简单快捷的方法，比如直接叫外卖？有时候复杂的算法就像满汉全席，而简单的解法就是那碗方便面！
5. **状态描述的足够性**：如果你发现你做的意大利面不够好吃（状态不足以描述问题），那就得考虑增加配料！比如加入更多的香料、蔬菜或者肉类，让这个菜更丰富。
### 实际例子：区间回文串
在你的栗子中，“区间回文串”的问题就像是找一种特殊的意大利面——它必须在上面和下面都看起来一样，也就是说，你要确保面条的排列可以正着吃也可以反着吃。这种情况下，可以通过从小到大的方式来转移，就像做法中的“逐步加热”一样。
当你写代码时，注意设置一个好的基准条件（例如从长度1的字符串开始），然后逐渐扩展，直到覆盖所有的情况。这样，你就能得到一个美味的“区间回文串”了！
希望这些解释能让你对区间DP有更清晰的认识！下次我们再聊聊如何处理那些复杂的“海鲜大餐”，哈哈！
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。 {:10_256:}{:10_256:} {:10_254:} 一天一学习 {:7_123:} {:10_257:} 呈现出 给 👌 666 {:10_269:}{:10_269:}{:10_269:}{:10_269:}{:10_269:}{:10_269:}
页:
[1]