[ABC325G] offence

题意

给定一个长度为 \(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;
}