zoj 3644 记忆化搜索

题目：给出一个有向图，从1到n，每个结点有个权值，每走一步，分值为结点权值的LCM，而且每一步的LCM都要有变化，问到达N的时候分值恰好为K的路径有多少条

记忆化搜索，虽然做过很多了，但是一直比较慢，这次总结出几点

1.注意确定终点状态

2.状态的初始化

3.不可能状态的排除

代码是参考cxlove写的，kuangbin博客要是刷完了，下一个就刷他啦

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<cmath>
 6 #include<queue>
 7 #include<map>
 8 using namespace std;
 9 #define MOD 1000000007
10 #define for0n for(i=0;i<n;i++)
11 #define for1n for(i=1;i<=n;i++)
12 #define for0m for(i=0;i<m;i++)
13 #define for1m for(i=1;i<=m;i++)
14 #define cl(a) memset(a,0,sizeof(a))
15 #define ts printf("*****
");
16 const int MAXN=2005;
17 const int MAXM=200005;
18 int n,m,tt,k;
19 int dp[MAXN][MAXN];
20 struct Edge
21 {
22     int to,next;
23 }edge[MAXM];
24 int head[MAXN],a[MAXN];
25 int tot;
26 void addedge(int u,int v)
27 {
28     edge[tot].to=v;
29     edge[tot].next=head[u];
30     head[u]=tot++;
31 }
32 void init()
33 {
34     tot=0;
35     memset(head,-1,sizeof(head));
36 }
37 map<int,int> fac;
38 int gcd(int a,int b)
39 {
40     return b==0?a:gcd(b,a%b);
41 }
42 int lcm(int a,int b)
43 {
44     return a/gcd(a,b)*b;
45 }
46 int dfs(int u,int val)
47 {
48     if(dp[u][fac[val]]!=-1) return dp[u][fac[val]];
49     if(u==n)    return val==k;
50     dp[u][fac[val]]=0;
51     for(int i=head[u];i!=-1;i=edge[i].next)
52     {
53         int v=edge[i].to;
54         if(k%a[v])  continue;
55         int temp=lcm(val,a[v]);
56         if(temp>k||temp==val) continue;
57         dp[u][fac[val]]=(dp[u][fac[val]]+dfs(v,temp))%MOD;
58     }
59     return dp[u][fac[val]];
60 }
61 int main()
62 {
63     int i,j;
64     #ifndef ONLINE_JUDGE
65     freopen("1.in","r",stdin);
66     #endif
67     while(scanf("%d%d%d",&n,&m,&k)!=EOF)
68     {
69         int u,v;
70         int q=1;
71         init();
72         for0m
73         {
74             scanf("%d%d",&u,&v);
75             addedge(u,v);
76         }
77         for(i=1;i*i<=k;i++)
78         {
79             if(k%i==0)
80             {
81                 fac[i]=q++;
82                 if(k/i!=i)  fac[k/i]=q++;
83             }
84         }
85         for1n
86         {
87             scanf("%d",&a[i]);
88         }
89         if(fac.find(a[1])==fac.end())   printf("0
");
90         else
91         {
92             memset(dp,-1,sizeof(dp));
93             printf("%d
",dfs(1,a[1]));
94         }
95     }
96 }