Problem Description 終于放寒假了，小明要和女朋友一起去看電影。這天，女朋友想給小明一個考驗，在小明正準備出發的時候，女朋友告訴他，她在電影院等他，小明過來的路線必須滿足給定的規則：
　　1、假設小明在的位置是1號點，女朋友在的位置是n號點，則他們之間有n-2個點可以走，小明每次走的時候只能走到比當前所在點編號大的位置；
　　2、小明來的時候不能按一定的順序經過某些地方。比如，如果女朋友告訴小明不能經過1 -> 2 -> 3，那么就要求小明來的時候走過的路徑不能包含有1 -> 2 -> 3這部分，但是1 -> 3 或者1 -> 2都是可以的，這樣的限制路徑可能有多條。
　　這讓小明非常頭痛，現在他把問題交給了你。
　　特別說明，如果1 2 3這三個點共線，但是小明是直接從1到3然后再從3繼續，那么此種情況是不認為小明經過了2這個點的。
　　現在，小明即想走最短的路盡快見到女朋友，又不想打破女朋友的規定，你能幫助小明解決這個問題嗎？

?

Input 輸入包含多組樣例，每組樣例首先包含兩個整數n和m，其中n代表有n個點，小明在1號點，女朋友在n號點，m代表小明的女朋友有m個要求；
　　接下來n行每行輸入2個整數x 和y（x和y均在int范圍），代表這n個點的位置（點的編號從1到n）；
　　再接著是m個要求，每個要求2行，首先一行是一個k，表示這個要求和k個點有關，然后是順序給出的k個點編號，代表小明不能走k1 -> k2 -> k3 ……-> ki這個順序的路徑；
　　n 和 m等于0的時候輸入結束。

　　[Technical Specification]
　　2 <= n <= 50
　　1 <= m <= 100
　　2 <= k <= 5

?

Output 對于每個樣例，如果存在滿足要求的最短路徑，請輸出這個最短路徑，結果保留兩位小數；否則，請輸出”Can not be reached!” （引號不用輸出）。

?

【題目大意】n個點，從1~n，每次只能走序號比之前序號大的，并且不能出現規定的順序，求1~n的最短路徑 【解題思路】 規定的順序可以看作AC自動機上的字符串，從一個節點到另外一個節點 因為如果上面的路徑沒有辦法到達的話，就說明下面的路徑也沒有辦法到達 之后，用dp去求 dp[ i ] [ j ]? 表示現在位置在第 i 個節點同時已經走到了AC自動機上的節點 j ，即已經經過了對應的路徑 然后枚舉狀態轉移 dp [ k ] [ t r i e [ j ] [ k ] ]? ?=? ?m i n ( d p [ k ] [ t r i e [ j ] [ k ] ] ,? ?d p [ i ] [ j ]? ?+? ?d i s ( i ,? ?k ) )? 從點 i 走到點 k ，AC自動機的節點從 j 到 k ，距離增加 dis（ i ，j ） 【注意】 數組的類型定義錯誤，改了一個小時QAQ 本來應該定義成double ，結果定義成了 i n t ，nmd #include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<queue> #include<vector> #include<cmath> using namespace std; const int MAXN = 6000; const int MAXM = 600; const double INF = 1e18; int trie[600][60],cnt; int fail[600],val[600],n,m,k; double dp[60][600]; struct node {double x, y; }a[60]; void insert(double *v) {int now = 0;for (int i = 1; i <=k; i++){int u = v[i];if (!trie[now][u]){trie[now][u] = ++cnt;}now = trie[now][u];}val[now]=1; } void get_fail() {int now = 0;queue<int> q;for (int i = 1; i <=n; i++)if (trie[now][i]){fail[trie[now][i]] = 0;q.push(trie[now][i]);}while (!q.empty()){int u = q.front(); q.pop();if (val[fail[u]])val[u]=1;for (int i = 1; i <=n; i++){int v = trie[u][i];if (v){fail[v] = trie[fail[u]][i];q.push(v);}else{trie[u][i] = trie[fail[u]][i];}}}return; } double dis(int i, int j) {double tmp = (a[i].x - a[j].x)*(a[i].x - a[j].x) + (a[i].y - a[j].y)*(a[i].y - a[j].y);return sqrt(tmp); } double v[600]; double solve() {double minn = INF;for (int i = 1; i <= n; i++)for (int j = 0; j <= cnt; j++)dp[i][j] = INF;dp[1][trie[0][1]] = 0;for (int i = 1; i <= n; i++){for (int j = 0; j <= cnt; j++){if (dp[i][j]<INF){for (int k = i + 1; k <= n; k++)if (!val[trie[j][k]])dp[k][trie[j][k]] = min(dp[k][trie[j][k]], dp[i][j] + dis(i, k));}}}for(int i=0;i<=cnt;i++)minn = min(minn, dp[n][i]);return minn; } int main() {while (scanf("%d%d", &n, &m) && n && m){cnt = 0;memset(trie, 0, sizeof(trie));memset(val, 0, sizeof(val));memset(fail, 0, sizeof(fail));for (int i = 1; i <= n; i++)scanf("%lf%lf", &a[i].x, &a[i].y);while(m--){scanf("%d", &k);for (int i = 1; i <= k; i++)scanf("%lf", &v[i]);insert(v);}get_fail();double ans = solve();if (ans >= INF)printf("Can not be reached!\n");elseprintf("%.2f\n", ans);}return 0; } View Code

?

轉載于:https://www.cnblogs.com/rentu/p/11336071.html

總結

以上是生活随笔為你收集整理的【HDU 4511】小明系列故事——女友的考验（AC自动机+DP）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。