比赛 20241021 评测结果 WWWWWWWWWW
题目名称 有机化学 最终得分 0
用户昵称 小金 运行时间 0.035 s
代码语言 C++ 内存使用 3.60 MiB
提交时间 2024-10-21 11:59:03
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int len,h[260],v[3010],ne[3010],e[3010],s[260],vis[260],tot,ans,d[260];
char a[260];
void chu()
{
	ans=0;
	tot=0;
	memset(h,0,sizeof(h));
	memset(e,0,sizeof(e));
	memset(ne,0,sizeof(ne));
	memset(vis,0,sizeof(vis));
	memset(s,0,sizeof(s));
	memset(v,0,sizeof(v));
	memset(d,0,sizeof(d));
}
void add(int x,int y)
{
	tot++;
	v[x]=y;
	ne[tot]=h[x];
	h[x]=tot;
	e[tot]=1;
	tot++;
	v[y]=x;
	ne[tot]=h[y];
	h[y]=tot;
	e[tot]=1;
}
void solve()
{
	for(int i=1;i<=len;i++)
	{
		if(a[i]=='H')
		{
			for(int j=i-1;j>=1;j--)
			{
				if(a[i]=='C'&&s[i]!=4)
				{
					s[i]++;
					break;
				}
			}
		}
	}
	for(int i=1;i<=len;i++)
	{
		if(a[i]=='C'&&s[i]!=4)
		{
			for(int j=i+1;j<=len;j++)
			{
				if(s[i]==4) break;
				if(a[j]=='C'&&s[j]!=4)
				{
					s[j]++;
					s[i]++;
					//cout<<i<<' '<<j<<endl;
					add(i,j);
				}
			}
		}
	}
}
void dp(int x) 
{
	vis[x]=1;
	for (int i=h[x];i;i=ne[i]) 
	{
		int y=v[i];
		if(vis[y]) continue;
		dp(y);
		ans=max(ans,d[x]+d[y]+e[i]);
		d[x]=max(d[x],d[y]+e[i]);
	}
}
int main()
{
	freopen("chemistryh.in","r",stdin);
    freopen("chemistryh.out","w",stdout);
	while(scanf("%s",a+1)!=EOF)
	{
		chu();
		len=strlen(a+1);
	    solve();
	    dp(1);
	    ans++;
	    printf("%d\n",ans);
	}
	return 0;
}