刚刚ABC的G
  • 板块学术版
  • 楼主chinaxjh
  • 当前回复19
  • 已保存回复19
  • 发布时间2022/8/13 21:45
  • 上次更新2023/10/27 15:33:00
查看原帖
刚刚ABC的G
136542
chinaxjh楼主2022/8/13 21:45

交流一下做法 个人想的是一个简单的dp再用一个奇怪的方法判无穷,但一直挂4个点

#include<bits/stdc++.h>
using namespace std;
#define fori(i,a,n) for(i=a;i<=n;i++)
#define ford(i,n,a) for(i=n;i>=a;i--)
typedef long long ll;
typedef double db;
typedef long double ld;
typedef unsigned long long ull;
typedef unsigned int uin;
//typedef __int128 lll;
const ll inf=1e15;
ll t[200][200][200],d[200][200],o[200],anss[200],f[200][200][200];
ll i,j,k,tt,n,ans;
string s;
int main()
{
	cin>>n;
	fori(i,1,n)
	{
		cin>>s>>k;
		if (s.size()==1) o[s[0]]=k;
		if (s.size()==2) d[s[0]][s[1]]=k;
		if (s.size()==3) t[s[0]][s[1]][s[2]]=k;
	}
	ans=-inf;
	fori(i,'a','z')
	ans=max(o[i],ans);
	fori(i,'a','z')
	 fori(j,'a','z')
	 f[2][i][j]=o[i]+o[j]+d[j][i],
	    ans=max(ans,f[2][i][j]);
	fori(i,3,100)
	{
		anss[i]=ans;
		fori(j,'a','z')
		 fori(k,'a','z')
		 {
		 	f[i][j][k]=f[i-1][k]['a']+o[j]+d[k][j]+t['a'][k][j];
		 	fori(tt,'b','z')
		    f[i][j][k]=max(f[i][j][k],f[i-1][k][tt]+o[j]+d[k][j]+t[tt][k][j]);
		    ans=max(ans,f[i][j][k]);
		 }
		  
	}
	 if (anss[60]==ans) cout<<ans<<endl;
	 else puts("Infinity");
	 
}

有没有过了的指点一下

2022/8/13 21:45
加载中...