ZOJ 3644 记忆化搜索

哎，只有牵扯到图，就啥都不会。。。。现在实在有必要学习一下，尤其像这道题，不是图论的DP题

基本上看爱神博客的吧

把握一点，就是无论到哪个点，当前值均为K的约数。

先求K的约数，离散化，DP[X][Y],代表到达第X的节点，数值为K的第Y个约数的路线数。

搜索的时候，参数为节点和值，由于随着搜索的深度加深，值一定会越来越大，避免了环路，于是就是个简单的搜索问题了，附代码：

#include <iostream> 
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <cmath>
#include <cstring>

#define ss(a) scanf("%d",&a)
#define mem(a,b) memset(a,b,sizeof(a))
#define N 2005
#define pb push_back
#define mod 1000000007
#define ll long long

using namespace std;

struct point
{
       int value;
       vector<int>next;
};

int dp[N][N/2],fac[N],n,k;
point a[N];

void init(int n)
{
     mem(dp,-1);mem(fac,0);
     for (int i=1;i<=n;i++) a[i].next.clear();
}

ll gcd(ll x,ll y)
{
          if (y==0) return x;
          else return gcd(y,x%y);
}

ll lcm(ll x,ll y)
{
          return x/gcd(x,y)*y;
}

int dfs(int x,int v)
{
     if (dp[x][v]!=-1) return dp[x][v];
     if (x==n) return (v==k);
     dp[x][v]=0;
     int i,z=a[x].next.size();
     for (i=0;i<z;i++)
     {
         int y,t;
         y=a[x].next[i];
         t=a[y].value;
         ll lc = lcm(v,t);
         if (v%t==0||lc>k) continue;
         dp[x][v]=(dp[x][v]+dfs(y,lc))%mod;
     }
     return dp[x][v];
}

int main()
{
    int i,m;
    while (ss(n)!=EOF)
    {
          ss(m);ss(k);
          init(n);
          while (m--)
          {
                int x,y;
                ss(x);ss(y);
                a[x].next.pb(y);      
          } 
          for (i=1;i<=n;i++) ss(a[i].value);
          int z=0;
          for (i=1;i*i>k;i++)
              if (k%i==0) 
              {
                          fac[i]=++z;
                          if (i*i!=k) fac[k/i]=++z;
              }
          printf("%d\n",dfs(1,a[1].value));
    }
    return 0;
}