给出一个长为 \(n\) 的字符串和非负整数 \(k\)。你可以进行以下操作若干次，使得最终字符串长度最小。
选择一个字串
of。然后删掉of以及这之后的 \(i\) 个字符。\(i\) 由你决定，但要满足 \(0\leq i\leq k\)。输出这个最小长度。\(1\leq n,k\leq 300\)。
做完以后感觉很简单。但是做的时候绕了个大大大大大的弯。
观察最终局面。在原字符串中的表现就是有若干连续段被删除。
设 \(F(l,r)\) 为子串 \([l,r]\) 的答案。
如果 \(F(l,r)\) 不能全部被删完（也就是有黑色部分），则一定存在一个 \(i\)，\(F(l,r)=F(l,i)+F(i+1,r)\)。
那做法就很显然了：
- 判断 \([l,r]\) 能否被删完。若能，\(F(l,r)=0\)。
- 否则，\(F(l,r)=\min\{F(l,i)+F(i+1,r)\}\)。
然后我一开始将这两个视作完全独立的问题。结果试了很久都没有试出咋判断。
后来啊，我有些绝望了。直到那一秒，我灵光一现。
我现在要找到对于可以完全删完的串的必要条件。观察 \(l\)，它一定要是 'o'。
后面要有一个 'f' 与它匹配。设第 \(i(a_i=f)\) 位与 \(l\) 匹配。
那么 \([l+1,i-1]\) 需要删完。\([i+1,r]\) 里有一些是这一次匹配顺便删的，剩下要删完。
想到这里我才明白。
第一个条件意味 \(F(l+1,i-1)=0\)。第二个意味 \(F(i+1,r)\leq k\)。
本来我使用了一个新的函数描述能否删干净。完全没有想到用第二个 \(\leq k\) 这个东西。
判断的方法已经很显然了。枚举 \(i\)，然后判断 \(F\)。
时间 \(O(n^3)\)。我一开始的尝试写的是记忆化，后来干脆全写记忆化了。
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define rg register
#define ld long double
#define ull unsigned long long
#define epb emplace_back
#define getc getchar
#define putc putchar
using namespace std;
inline int re() {
rg int x=0,p=0;rg char c=getchar();
while(c<'0'||c>'9') (!p)?(p=c=='-'):(p=p),c=getchar();
while('0'<=c&&c<='9') (x*=10)+=c-48,c=getchar();
if(p) x=-x;
return x;
}
inline void wt(rg int x) { if(x>9) wt(x/10);putc(x%10+48); }
const int N=305;
int n,k,f[N][N],ans=10000;
char a[N];
int F(int l,int r) {
if(f[l][r]!=100000) return f[l][r];
int ret=0;
{
if(l>r) ret=1;
else if(r-l+1==1||a[l]!='o') ret=0;
else {
if(a[l+1]=='f'&&F(l+2,r)<=k) {
ret=1;
} else {
for(int i=l+1;i<=r;i++) {
if(a[i]=='f'&&F(i+1,r)<=k&&F(l+1,i-1)==0) {
ret=1;
break;
}
}
}
}
}
if(ret) return f[l][r]=0;
for(int i=l;i<r;i++) f[l][r]=min(f[l][r],F(l,i)+F(i+1,r));
return f[l][r];
}
int main() {
// freopen(".in","r",stdin),freopen(".out","w",stdout);
scanf("%s",a+1);
n=strlen(a+1);k=re();
for(int i=1;i<=n;i++) for(int j=i;j<=n;j++) f[i][j]=i==j?1:100000;
wt(F(1,n));
}