[HOJ 179][Codeforces #121]爆炸的期中考

HOJ生病惹QQ，因此我在這裡做了題目備份，請參考～

因為一定要照著順序把國王的名字串起來，所以可以考慮維護一個陣列ANS[i][j]代表開頭字母i結尾字母j的名字目前最長可以串到多長
初始化: {ANS[i][i]=0, a<=i<=z}, {ANS[i][j]=-INF, i!=j}(因為剛開始沒有名字可以串成開頭i結尾j的字串) 然後對於目前讀到的名字，假設是abcd好了，那就可以把所有ANS[i][d]用ANS[i][a]+4來更新最大值，可以發現中間的bc其實沒什麼作用，只是讓名字長度變4而已XD
最後，max{ANS[i][i], a<=i<=z}就是答案了(因為最後一個國王的名字結尾要和第一個國王的名字開頭一樣)

code:

#include<cstdio>
#include<vector>
#include<map>
#include<cassert>
using namespace std;
const int INF=2147483647;
void getmax(int &a,const int b){if(b>a)a=b;}
int M,ANS[26][26];
int main()
{
//    freopen("in.txt","r",stdin);
    static int testcase;scanf("%d",&testcase);
    while(testcase--)
    {
        scanf("%d",&M);
        for(int i=0;i<26;i++)for(int j=0;j<26;j++)ANS[i][j]=-INF;
        for(int i=0;i<26;i++)ANS[i][i]=0;
        for(int i=0;i<M;i++)
        {
            static char name[11];scanf("%s",name);
            int len=-1;while(name[++len]);
            const int a=name[0]-'a',b=name[len-1]-'a';
            static int tmp[26];
            for(int j=0;j<26;j++)
            {
                if(ANS[j][a]==-INF)tmp[j]=-INF;
                else tmp[j]=ANS[j][a]+len;
            }
            for(int j=0;j<26;j++)getmax(ANS[j][b],tmp[j]);
        }
        int ans=-INF;
        for(int i=0;i<26;i++)getmax(ans,ANS[i][i]);
        printf("%d\n",ans==-INF?0:ans);
    }
    return 0;
}