小明系列故事――女友的考验 HDU - 4511 AC自动机+简单DP-白红宇

小明系列故事――女友的考验 HDU - 4511 AC自动机+简单DP

阅读量：5030 次

发布时间：2019-06-12

本文共 2284 字，大约阅读时间需要 7 分钟。

题意：自己看题目，中文体面。

题解：

把所有不能走的路径放入AC自动机中。

然后DP【i】【j】表示走到 i 这个点，且位于AC自动机 j 这个节点最短距离

然后直接DP即可。注意一点会爆int

1 #include 
      
         2 #include 
         3 #include 
        
           4 #include 
         
            5 #include 
          
             6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #include 
              
                10 #include 
               
                 11 #include 
                
                  12 #include 
                 
                   13 #include 
                  
                    14 15 #define pi acos(-1.0) 16 #define eps 1e-9 17 #define fi first 18 #define se second 19 #define rtl rt<<1 20 #define rtr rt<<1|1 21 #define bug printf("******\n") 22 #define mem(a, b) memset(a,b,sizeof(a)) 23 #define name2str(x) #x 24 #define fuck(x) cout<<#x" = "<
                   
                    <

Q; 85 fail[root] = root; 86 for (int i = 0; i < 52; i++) 87 if (next[root][i] == -1) next[root][i] = root; 88 else { 89 fail[next[root][i]] = root; 90 Q.push(next[root][i]); 91 } 92 while (!Q.empty()) { 93 int now = Q.front(); 94 Q.pop(); 95 if (End[fail[now]]) End[now] = 1; 96 for (int i = 0; i < 52; i++) 97 if (next[now][i] == -1) next[now][i] = next[fail[now]][i]; 98 else { 99 fail[next[now][i]] = next[fail[now]][i];100 Q.push(next[now][i]);101 }102 }103 }104 105 double dp[52][510];106 107 void solve() {108 for (int i = 0; i <= n; ++i)109 for (int j = 0; j < cnt; ++j)110 dp[i][j] = INFLL;111 dp[1][next[root][1]] = 0;112 for (int i = 1; i <= n; ++i) {113 for (int j = 0; j < cnt; ++j) {114 if (dp[i][j] == INFLL) continue;115 for (int k = i + 1; k <= n; ++k) {116 int idx = next[j][k];117 if (End[idx]) continue;118 dp[k][idx] = min(dp[k][idx], dp[i][j] + cal(i, k));119 }120 }121 }122 double ans = INFLL;123 for (int i = 0; i < cnt; ++i) ans = min(ans, dp[n][i]);124 if (ans == INFLL) printf("Can not be reached!\n");125 else printf("%.2f\n", ans);126 }127 128 void debug() {129 for (int i = 0; i < cnt; i++) {130 printf("id = %3d,fail = %3d,end = %3d,chi = [", i, fail[i], End[i]);131 for (int j = 0; j < 26; j++) printf("%2d", next[i][j]);132 printf("]\n");133 }134 }135 } ac;136 137 int main() {138 // FIN;139 while (~sffi(n, m)) {140 if (n == 0 && m == 0) break;141 for (int i = 1; i <= n; ++i) sffi(x[i], y[i]);142 ac.init();143 for (int i = 0; i < m; ++i) {144 sfi(k);145 for (int j = 0; j < k; ++j) sfi(buf[j]);146 ac.insert(k);147 }148 ac.build();149 ac.solve();150 }151 return 0;152 }

View Code

转载于:https://www.cnblogs.com/qldabiaoge/p/11379739.html

你可能感兴趣的文章