解法1 玄学剪枝
最暴力的dfs是很好打的 交上去有70
考虑如何剪枝
1.当一个单词首尾和另外一个单词相同时，优先选择最长的那个，其他的不用选。 这一点很好实现，给原数组排个序，dfs的时候写个while特判一下就好
2.卡时自杀式剪枝 你懂我意思吧
以上两个剪枝随便加一个都可以过。。。
解法2 状压dp
n<=16 应该要先存下所有单词选与不选的情况
考虑到只和一个单词的开头结尾有关 那么设f[i][j]表示状态为i 结尾字母为j的最大值
然后枚举所有状态 对于每个状态 选其中的一个字符串作为最后选进来的 更新当前f
解法1代码
#include<bits/stdc++.h> using namespace std; int n,ans,tim; string s; struct W { int len; char begin,end; bool vis; }word[20]; void dfs(int now,int len,int cnt) { ans=max(ans,len); if(clock()-tim>10000) //自杀式剪枝 { cout<<ans; exit(0); } for(int i=1;i<=n;i++) { if(!word[i].vis&&word[now].end==word[i].begin) { word[i].vis=true; dfs(i,len+word[i].len,cnt+1); word[i].vis=false; while(word[i+1].begin==word[i].begin&&word[i+1].end==word[i].end) i++; } } } inline bool cmp(const W &a,const W &b) { if(a.begin!=b.begin) return a.begin<b.begin; else if(a.end!=b.end) return a.end<b.end; else return a.len>b.len; } int main() { tim=clock(); cin>>n; for(int i=1;i<=n;i++) { cin>>s; word[i].len=s.length(); word[i].begin=s[0]; word[i].end=s[word[i].len-1]; word[i].vis=false; } sort(word+1,word+n+1,cmp); for(int i=1;i<=n;i++) { word[i].vis=true; dfs(i,word[i].len,1); word[i].vis=false; } cout<<ans; return 0; }解法2代码
#include<bits/stdc++.h> #define N 17 using namespace std; int n,f[1<<N][10],ans; struct S { int begin,end,len; }word[N]; inline int index(char ch) { if(ch=='A') return 1; if(ch=='E') return 2; if(ch=='I') return 3; if(ch=='O') return 4; if(ch=='U') return 5; } int main() { cin>>n; for(int i=1;i<=n;i++) { string s; cin>>s; word[i].len=s.length(); word[i].begin=index(s[0]); word[i].end=index(s[word[i].len-1]); } int ans=0; for(int i=0;i<(1<<n);i++) { for(int j=1;j<=n;j++) { if(i&(1<<(j-1))) //j在当前状态中存在 { f[i][word[j].end]=max(f[i][word[j].end],f[i-(1<<(j-1))][word[j].begin]+word[j].len); ans=max(ans,f[i][word[j].end]); } } } cout<<ans; return 0; }转载于:https://www.cnblogs.com/Patrickpwq/articles/9807802.html
