带权有向图上点不重复的最长路径 状压dp

来自仓鼠老师的话：

这题实际上就是带权有向图上点不重复的最长路径。从理论上来说，应该是个NP问题。

就是把每一句话设为一个点，然后可以\(O(n^2)\)的连边，怎么连边就不说了吧。。

设dp[i][j]为当前走到\(i\)点，已走的状态为\(j\)。然后就可以愉快地进行状压dp。

有一个经验性总结：枚举状态的那一维一定要放在前面！不然答案是错的！我已经亲身经历过3次了！

今年再来出状压dp哩

代码：

#include
    
     #include
     
      #include
      
       const int maxn = 17;struct Edges{    int next, to;} e[maxn * maxn];int head[maxn], tot;int start[maxn], end[maxn];int weight[maxn];int dp[maxn][65537];int n;int id(char x){    if(x == 'A') return 1;    else if(x == 'E') return 2;    else if(x == 'I') return 3;    else if(x == 'O') return 4;    else if(x == 'U') return 5;}void link(int u, int v){    e[++tot] = (Edges){head[u], v};    head[u] = tot;}int main(){    scanf("%d", &n);    for(int i = 1; i <= n; i++)    {        char ch[105]; scanf("%s", ch);        start[i] = id(ch[0]);        int len = strlen(ch);        end[i] = id(ch[len - 1]);        weight[i] = len;    }    for(int i = 1; i <= n; i++)    {        for(int j = 1; j <= n; j++)        {            if(end[i] == start[j]) link(i, j);        }    }    int S = (1 << n) - 1;    for(int i = 1; i <= n; i++) dp[i][1 << (i - 1)] = weight[i];    for(int j = 1; j <= S; j++)    {        for(int i = 1; i <= n; i++)        {            if((1 << (i - 1)) & j)            {                for(int k = head[i]; k; k = e[k].next)                {                    int v = e[k].to;                    if((1 << (v - 1)) & j) continue;                    dp[v][j | (1 << (v - 1))] = std::max(dp[v][j | (1 << (v - 1))], dp[i][j] + weight[v]);                }            }        }    }    int ans = 0;    for(int i = 1; i <= n; i++)    {        for(int j = 1; j <= S; j++)        {            ans = std::max(ans, dp[i][j]);        }    }    printf("%d\n", ans);    return 0;}