题意
给定一个长度为 \(n\) 字符串以及一个数 \(f\)，你可以执行以下操作任意次，求最终字符串长度的最小值。
- 在字符串中选择一个连续的
of，删掉它以及它后面的 \(i\) 个字符，\(0 \le i \le f\)。
数据范围：\(n \le 300\)。
思路
看到数据范围以及字符串中间的删除可以想到区间 dp。
设 \(dp_{i,j}\) 表示 \(i\) 到 \(j\) 这一段字符串最少能被删到几个。那么我们可以枚举左右端点 \(i,j\) 以及中间点 \(k\)，如果满足 \(s_{i}=o\)，\(s_{k}=f\) 并且 \(i+1\) 到 \(k-1\) 这一段可以被删完的话，那么就有转移 \(dp_{i,j}=\max(0,dp_{k+1,j}-f)\)。最终的答案就是 \(dp_{1,n}\)。
要初始化。
Code
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define inf 0x3f
const int MAXN = 1e3 + 10;
int f,n,dp[MAXN][MAXN];
char s[MAXN];
signed main()
{
memset(dp,inf,sizeof dp);
cin >> (s + 1) >> f;
int n = strlen(s + 1);
for(int i = 1;i <= n + 1;i++) dp[i][i] = 1,dp[i][i - 1] = 0;
for(int i = 1;i < n;i++)
{
if(s[i] == 'o' && s[i + 1] == 'f') dp[i][i + 1] = 0;
else dp[i][i + 1] = 2;
}
for(int len = 3;len <= n;len++)
for(int i = 1;i <= n - len + 1;i++)
{
int j = i + len - 1;
dp[i][j] = min(dp[i + 1][j],dp[i][j - 1]) + 1;
if(s[i] != 'o') continue;
for(int k = i + 1;k <= j;k++)
{
if(s[k] == 'f' && dp[i + 1][k - 1] == 0)
dp[i][j] = min(dp[i][j],max(0ll,dp[k + 1][j] - f));
}
}
cout << dp[1][n];
return 0;
}