zoj 3644(최소 공배수 DP 정보)

2147 단어 structiterator
이 제목은 반드시 기록해야 한다, 경전.
dp[i][j]i는 현재 어느 점에 있는지 표시하고 j는 현재 몇 번째 약수를 나타낸다. 기억화 검색을 하면 된다. 몇 가지 문제를 풀고 나서 이것은 고전적인 설정 상태 방법이라는 것을 발견했다.
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<map>
#define MOD 1000000007
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
#define LL long long
using namespace std;
const int maxn = 20005;
struct edge
{
    int u,v,next;
}e[maxn];
map<LL,int> mp;
int n,m,K,dp[2005][1005];
int head[2005],tot,get[2005];
void add_edge(int u,int v);
int dfs(int now,LL x);
void init();
LL gcd(LL a,LL b){
    return b==0?a:gcd(b,a%b);
}//     
LL lcm(LL a,LL b){
    return a/gcd(a,b)*b;
}//     
int main()
{
    int i;
    while(scanf("%d%d%d",&n,&m,&K) != EOF)
    {
        memset(dp,-1,sizeof(dp));
        memset(head,-1,sizeof(head));
        tot = 0;
        for(i = 0;i < m;i ++)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            add_edge(u,v);
        }
        for(i = 1;i <= n;i ++) scanf("%d",&get[i]);
        init();
        if(mp.find(get[1]) == mp.end())
        {
            printf("0
"); continue; } printf("%d
",dfs(1,get[1])); } return 0; } void add_edge(int u,int v) { e[tot].u = u,e[tot].v = v; e[tot].next = head[u],head[u] = tot ++; } void init() { int i,j,cnt = 0; mp.clear(); for(i = 1;i <= sqrt(K);i ++) { if(K % i) continue; mp[i] = cnt ++; mp[K / i] = cnt ++; } } int dfs(int now,LL x) { if(dp[now][mp[x]] != -1) return dp[now][mp[x]]; if(now == n) { if(x == K) return dp[now][mp[x]] = 1; else return dp[now][mp[x]] = 0; } int i,sum = 0; map<LL,int>:: iterator it; for(i = head[now];i != -1;i = e[i].next) { int v = e[i].v; LL y = lcm(x,get[v]); if(y == x) continue; it = mp.find(y); if(it == mp.end()) continue; sum += dfs(v,y); sum %= MOD; } return dp[now][mp[x]] = sum; }

좋은 웹페이지 즐겨찾기