POJ2004 Mix and Build
良問だと思う。文字列の長さをL,文字列数をNとすると,O(N L^2 log N).
TLEぎりぎりでAC.
#include<stdio.h> #include<vector> #include<algorithm> #include<string> #include<iostream> using namespace std; typedef pair<string,int>psi; typedef pair<int,psi>pisi; int len[10000]; int frm[10000]; int main() { vector<string>zvec; vector<pisi>vec; for(int i=0;;i++) { string zan; if(!(cin>>zan)) { break; } zvec.push_back(zan); sort(zan.begin(),zan.end()); vec.push_back(make_pair(zan.size(),make_pair(zan,i))); } sort(vec.begin(),vec.end()); int maxi=0,nn; for(int i=0;i<vec.size();i++) { frm[i]=i; len[i]=0; for(int j=0;j<vec[i].second.first.size();j++) { string subs=vec[i].second.first.substr(0,j)+vec[i].second.first.substr(j+1); int low=lower_bound(vec.begin(),vec.begin()+i,make_pair(int(vec[i].second.first.size())-1,make_pair(subs,0)))-vec.begin(); if(vec[low].second.first==subs) { if(len[i]<len[low]+1) { len[i]=len[low]+1; frm[i]=low; } } } if(len[i]>maxi) { maxi=len[i]; nn=i; } } vector<int>ans; for(;;) { ans.push_back(nn); if(frm[nn]==nn) { break; } nn=frm[nn]; } reverse(ans.begin(),ans.end()); for(int i=0;i<ans.size();i++) { cout<<zvec[vec[ans[i]].second.second]<<endl; } }