题解 P1019 【单词接龙】
糪眾脦颰罷
2019-02-10 19:57:11
# 注：本题不一样的解法
## 其实这道题可以状压dp的
我们先谈一下怎么状压dp：
### 状态定义：
**$dp\left[i\right]\left[j\right]$表示情况i下以j号单词结尾所能达到的最大长度**
我们可以用1个长度为n的01串（即二进制）表示单词使用情况，1表示使用过，0表示未使用。
举几个栗子：
- n=4时，1101表示只使用过1，3和4号单词；
- n=5时，10010表示只使用过5号和2号单词。
**注意**：在我写的（不包括你）01串中，**第i位表示的是第n-i+1号单词的情况**原因后面会提到
### 状态转移方程：
$dp\left[next\right]\left[j\right]=max\{dp\left[next\right]\left[j\right], dp\left[now\right]\left[k1...kn\right]+len\left[k1...kn\right]\left[j\right]\}$
其中k1...kn表示枚举n个单词，$len\left[k\right]\left[j\right]$表示将j号单词接在k号后面长度的增加量（可预处理）
### dp部分代码
```
for(int i=1;i<(1<<n);i++){\\总共有2^n种使用情况
for(int j=1;j<=n;j++){
if(i&(1<<(j-1)))continue;\\判断j在i情况下有没有被使用过
for(int k=1;k<=n;k++){
if((i&(1<<(k-1)))&&len[k][j]!=-1&&dp[i][k]!=-1){\\判断能否转移：1.k在情况i下使用了 2.j能接在k后面
dp[i|(1<<(j-1))][j]=max(dp[i|(1<<(j-1))][j],dp[i][k]+len[k][j]);\\转移：next=i|(1<<(j-1)),now=i;
ans=max(ans,dp[i|(1<<(j-1))][j]);\\注意不断更新最终结果
}
}
}
}
```
**还有一点，本题中由于么个单词可以最多用两次，所以应该开个$2*n$长度的数组，将每个单词再复制一遍**
其他没什么好说的了，详见代码。。。
------------
```
#include<bits/stdc++.h>
using namespace std;
int n,len[1001][1001],dp[1<<16][17],ans;
string s[1001];
char tou;
void pre(){\\预处理len数组，有点小麻烦
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==j)continue;
int lenans=0;
for(int lenth=1;lenth<min(s[i].size(),s[j].size());lenth++){
bool flag=true;
for(int i1=s[i].size()-lenth,j1=0;i1<=s[i].size()-1,j1<=lenth-1;i1++,j1++){
if(s[i][i1]!=s[j][j1]){
flag=false;
break;
}
}
if(flag==true)lenans=lenth;
if(lenans!=0)break;
}
if(lenans==0)len[i][j]=-1;
else len[i][j]=s[j].size()-lenans;
}
}
}
int main(){
memset(dp,-1,sizeof(dp));
scanf("%d",&n);
for(int i=1;i<=n;i++)cin>>s[i];
for(int i=n+1;i<=2*n;i++)s[i]=s[i-n];\\复制
n=n*2;
pre();\\预处理
scanf("\n%c",&tou);\\这里得加个"\n",因为数字读入之后后面还有个换行符
for(int i=1;i<=n;i++){\\特别处理开头单词的情况
if(s[i][0]==tou){
dp[1<<(i-1)][i]=s[i].size();
ans=max(ans,dp[1<<(i-1)][i]);\\注意这里也要更新ans(我被卡过一次)
}
}
for(int i=1;i<(1<<n);i++){\\开始dp
for(int j=1;j<=n;j++){
if(i&(1<<(j-1)))continue;
for(int k=1;k<=n;k++){
if((i&(1<<(k-1)))&&len[k][j]!=-1&&dp[i][k]!=-1){
dp[i|(1<<(j-1))][j]=max(dp[i|(1<<(j-1))][j],dp[i][k]+len[k][j]);
ans=max(ans,dp[i|(1<<(j-1))][j]);
}
}
}
}
printf("%d",ans);
return 0;\\大功告成
}
```