为什么WA了9个点
查看原帖
为什么WA了9个点
334041
沉鸣cmh楼主2020/8/30 14:41

怎么错了这么多,能改吗,还是记搜不行。。。

#include<bits/stdc++.h>
using namespace std;
int n,k,a[505],su[505][105][3],sum;
char oo;
int dfs(int wz,int cs){int th;
	if(su[wz][cs][a[wz]])return su[wz][cs][a[wz]];
	if(cs==0||wz==n+1)return 0;
	if(a[wz]==1){
	th=dfs(wz+1,cs),a[wz]=0;
	th=max(th,dfs(a[wz]+1,cs-1)+(a[wz-1]==0?-1:0)+(a[wz+1]==1?1:0));a[wz]=0;
	}
	else {
	th=dfs(wz+1,cs),a[wz]=1;
	th=max(th,dfs(a[wz]+1,cs-1)+(a[wz-1]==0?1:0)+(a[wz+1]==1?-1:0));
	}
	return su[wz][cs][a[wz]]=th;
}
int main(){a[0]=3;
	cin>>n>>k;
	for(int i=1;i<=n;i++){
	cin>>oo;if(oo=='z'){a[i]=1;if(a[i-1]==0)sum++;}else a[i]=0;
	}
	cout<<dfs(1,k)+sum;
	return 0;
}
2020/8/30 14:41
加载中...