交流一下做法 个人想的是一个简单的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");
}
有没有过了的指点一下