求hack
查看原帖
求hack
552699
_aknoip_楼主2023/12/3 15:19

45分,求hack

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
string s;
int a[N],f[9],g[9],h[N],h2[N],sum[N],dp[N],dpg[N],ans=1e9,n; 
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>s;
	n=s.size();
	s='0'+s;
	for(int i=1;i<=n;i++)cin>>a[i],sum[i]=sum[i-1]+a[i];
	for(int i=1;i<=n;i++){
		if(s[i]=='b')f[1]=i,g[1]=a[i];
		if(s[i]=='e'){
			if(f[5]>f[6]||(f[5]==f[6]&&g[5]+a[i]>g[6]))g[6]=g[5]+a[i],f[6]=f[5];
			if(f[1]>f[2]||(f[1]==f[2]&&g[1]+a[i]>g[2]))g[2]=g[1]+a[i],f[2]=f[1];
		}
		if(s[i]=='s'){
			if(f[3]>f[4]||(f[3]==f[4]&&g[3]+a[i]>g[4]))g[4]=g[3]+a[i],f[4]=f[3];
			if(f[2]>f[3]||(f[2]==f[3]&&g[2]+a[i]>g[3]))g[3]=g[2]+a[i],f[3]=f[2];
		}
		if(s[i]=='i'){
			if(f[4]>f[5]||(f[4]==f[5]&&g[4]+a[i]>g[5]))g[5]=g[4]+a[i],f[5]=f[4];
		}
		if(s[i]=='e')h[i]=f[6],h2[i]=g[6];
	}
	for(int i=1;i<=n;i++){
		if(!h[i])dp[i]=dp[i-1],dpg[i]=dpg[i-1];
		else{
			if(dp[i-1]==dp[h[i]-1]+1)dp[i]=dp[i-1],dpg[i]=min(dpg[h[i]-1]+sum[i]-sum[h[i]-1]-h2[i],dpg[i-1]);
			else if(dp[i-1]<dp[h[i]-1]+1)dp[i]=dp[h[i]-1]+1,dpg[i]=dpg[h[i]-1]+sum[i]-sum[h[i]-1]-h2[i];
		}
	}
	for(int i=n;i>=1;i--){
		if(dp[i]==dp[n])ans=min(ans,dpg[i]);
	}
	cout<<dp[n]<<"\n"<<ans;
	return 0;
}
2023/12/3 15:19
加载中...