首页 > 代码库 > HDU 4511 (AC自动机+状态压缩DP)
HDU 4511 (AC自动机+状态压缩DP)
题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=4511
题目大意：从1走到N，中间可以选择性经过某些点，比如1->N，或1->2->N，但是某些段路径（注意不是某些条）是被禁止的。问从1->N的最短距离。
解题思路：
AC自动机部分：
如果只是禁掉某些边，最短路算法加提前标记被禁的边即可。
但是本题是禁掉指定的路段，所以得边走边禁，需要一个在线算法。
所以使用AC自动机来压缩路段，如禁掉的路段是1->2->3，那么insert字符串（123) ，注意点只有1~50，所以0~50用ASCII 压缩成字符串即可。
这样就能够完成禁止路段的在线状态转移。
状态压缩DP部分：
其实就是手艹一个两点之间的最短路。dp[i][j]表示在地点i，当前字符是j的状态。
初始化：fill（&dp0][0],&dp[maxn-1][maxp-1],inf)，inf=1e12，double的inf很头疼，memset是不能用的。
边界：首先找下出发点在pool中的位置，s=root->next[0]，如果s被禁，那么就不用算了。否则dp[0][s]=0;
方程: dp[k][t]=min(dp[k][t],dp[i][j]+dist(i,k))
答案：min(dp[n-1][0..cnt])
解释下方程，其中for(0...i...n-1)，for(i+1...k....n) ，枚举两个点。
然后就是中间多出的AC自动机的状态压缩for(0....j....cnt)，负责打出所有的路径转移状态。
#include "cstdio"#include "cstring"#include "string"#include "iostream"#include "queue"#include "math.h"using namespace std;#define maxn 55#define maxp 10*100#define inf 1e12struct Point{ double x,y;}P[maxn];struct Trie{ Trie *next[maxn],*fail; int cnt;}pool[maxp],*root,*sz;int pre,now;double dp[55][maxp];Trie *newnode(){ Trie *ret=sz++; memset(ret->next,0,sizeof(ret->next)); ret->fail=0; ret->cnt=0; return ret;}void init(){ sz=pool; root=newnode();}void Insert(string str){ Trie *pos=root; for(int i=0;i<str.size();i++) { int c=str[i]; if(!pos->next[c]) pos->next[c]=newnode(); pos=pos->next[c]; } pos->cnt++;}void getfail(){ queue<Trie *> Q; for(int c=0;c<maxn;c++) { if(root->next[c]) { root->next[c]->fail=root; Q.push(root->next[c]); } else root->next[c]=root; } while(!Q.empty()) { Trie *x=Q.front();Q.pop(); for(int c=0;c<maxn;c++) { if(x->next[c]) { x->next[c]->fail=x->fail->next[c]; x->next[c]->cnt+=x->fail->next[c]->cnt; Q.push(x->next[c]); } else x->next[c]=x->fail->next[c]; } }}double dist(Point a,Point b) {return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}int main(){ //freopen("in.txt","r",stdin); int n,m,k,p; while(scanf("%d%d",&n,&m)!=EOF&&n) { init(); for(int i=0;i<n;i++) scanf("%lf%lf",&P[i].x,&P[i].y); for(int i=1;i<=m;i++) { scanf("%d",&k); string tt; for(int i=1;i<=k;i++) { scanf("%d",&p); tt.push_back(p-1); } Insert(tt); } getfail(); int s=root->next[0]-pool; if(root->next[0]->cnt) printf("Can not be reached!\n"); else { int cnt=sz-pool; fill(&dp[0][0],&dp[54][maxp-1],inf); dp[0][s]=0; for(int i=0; i<n-1; i++) { for(int j=0; j<cnt; j++) { Trie *pos=pool+j; for(int k=i+1; k<n; k++) { if(pos->next[k]->cnt) continue; int t=pos->next[k]-pool; dp[k][t]=min(dp[k][t],dp[i][j]+dist(P[i],P[k])); } } } double ans=inf; for(int i=0; i<cnt; i++) ans=min(ans,dp[n-1][i]); if(ans==inf) printf("Can not be reached!\n"); else printf("%.2lf\n",ans); } }}
| 11848330 | 2014-10-11 14:48:53 | Accepted | 4511 | 109MS | 748K | 2865B | C++ | Physcal |
HDU 4511 (AC自动机+状态压缩DP)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。