這道題目竟然真的ac了,好神奇啊。
當時算的時間復雜度為O(T*N!),理論值達到7kw。
做法:
預處理dp數組,使得dp[i][j]代表j放在i後面長度的增加值。
然後dfs,dfs的時候要注意,用一個二進制數標記當前狀態。
二進制中0代表當前位置已取,1代表當前位置未取。每次查找二進制的子狀態。
然後看看哪個位置在子狀態消失了。
一定要直接查找子狀態。
#include#include #include #include using namespace std; char str[31][31]; int dp[31][31]; int vis[31]; int n; int ans; int fc[(1<<21)]; int houji(int x,int y) { int i,j; int len1=strlen(str[x]); int len2=strlen(str[y]); for(i=0;i