KEYENCE Programming Contest 2023 Autumn（AtCoder Beginner Contest 325）G. offence(带删区间dp)

题目

给定小写字母串s(|s|<=300)，以及一个上限k(k<=300)，

每次操作，你可以选择当前串中的一个of子串，

删除of子串和of子串后面紧跟着的i个字符，其中i∈[0,k]，删完之后串后面的部分会接上来

你可以执行任意次操作，也可以不执行，求串最少剩的长度是多少

思路来源

乱搞ac

心得

1. 一开始没考虑到删除的后面k个字符非连续的情形，于是是枚举的删到哪里，然后wa了

非连续是指，先删后面的一段of，再删前面的of，导致第二次删的在原串中不一定连续

2. 发现这个点之后，想了很久，一开始是想加一维表示还能最多用多少次删的机会，

后来想了想发现这个值可以和dp维护的最小剩的数量合并，直接减k就可以了

3. 减k之后，一开始没考虑s[l]=='o'时dfs(l+1,r)，

后来加上枚举划分轴通过了，但是不知道怎么通过的，直至申老师构造出了一种样例

oofaaa

3

此时，如果不舍弃掉第一个o的话，就得不到ans=1的答案

也就是不一定每个o都是要和f匹配的，舍弃当前o，也是一种决策

题解

其实就是枚举每个o的决策，假设当前在[l,r]

1. 如果s[l]不为'o'，舍弃当前字符，考虑[l+1,r]

否则，s[l]='o'

① 舍弃当前o，考虑[l+1,r]

② 串最左侧是of，考虑[l+2,r]删完后最少剩几个字符，还可以减k

③ 串最左侧是o，中间第i个字符是f，但o和f之间这一段可以被删完，

那么先删完这一段，再用这个of，考虑[i+1,r]删完后最少剩几个字符，还可以减k

代码1

加上舍弃o的决策

#include<bits/stdc++.h>
using namespace std;
const int N=305;
char s[N];
int n,k,dp[N][N];
int dfs(int l,int r){
	if(l>r)return 0;
	int &ans=dp[l][r];
	if(~ans)return ans;
	if(l==r)return ans=1;
	ans=min(r-l+1,1+dfs(l+1,r));
	if(s[l]=='o'){
		for(int i=l+1;i<=r;++i){
			if(s[i]=='f' && dfs(l+1,i-1)==0){
				ans=min(ans,dfs(i+1,r)-k);
			}
		}
		ans=max(ans,0);
	}
	return ans;
}
int main(){
	memset(dp,-1,sizeof dp);
	scanf("%s",s+1);
	n=strlen(s+1);
	scanf("%d",&k);
	printf("%d\n",dfs(1,n));
	return 0;
}

代码2

不加舍弃o的决策，但枚举划分轴

#include<bits/stdc++.h>
using namespace std;
const int N=305;
char s[N];
int n,k,dp[N][N];
int dfs(int l,int r){
	if(l>r)return 0;
	int &ans=dp[l][r];
	if(~ans)return ans;
	if(l==r)return ans=1;
	if(s[l]!='o')return ans=1+dfs(l+1,r);
	ans=r-l+1;
	for(int i=l+1;i<=r;++i){
		if(s[i]=='f' && dfs(l+1,i-1)==0){
			ans=min(ans,dfs(i+1,r)-k);
		}
	}
	for(int i=l;i<r;++i){
		ans=min(ans,dfs(l,i)+dfs(i+1,r));
	}
	ans=max(ans,0);
	return ans;
}
int main(){
	//while(1){
		memset(dp,-1,sizeof dp);
		//scanf("%d",&n);
		scanf("%s",s+1);
		n=strlen(s+1);
		scanf("%d",&k);
		printf("%d\n",dfs(1,n));
	//}
	return 0;
}

代码3

把记忆化搜索改成递推，需要按长度从小到大

#include<bits/stdc++.h>
using namespace std;
const int N=305;
char s[N];
int n,k,dp[N][N];
int main(){
	scanf("%s",s+1);
	n=strlen(s+1);
	scanf("%d",&k);
	for(int len=1;len<=n;++len){
		for(int l=1;l+len-1<=n;++l){
			int r=l+len-1;
			if(len==1)dp[l][r]=1;
			else if(s[l]!='o')dp[l][r]=dp[l+1][r]+1;
			else{
				dp[l][r]=r-l+1;
				for(int i=l+1;i<=r;++i){
					if(s[i]=='f' && !dp[l+1][i-1]){
						dp[l][r]=min(dp[l][r],dp[i+1][r]-k);
					}
					dp[l][r]=min(dp[l][r],dp[l][i-1]+dp[i][r]);
				}
				dp[l][r]=max(dp[l][r],0);
			}
			//printf("l:%d r:%d dp:%d\n",l,r,dp[l][r]);
		}
	}
	printf("%d\n",dp[1][n]);
	return 0;
}