ZOJ 3644 Kitty's Game(상태 단순화 & DP)

2401 단어
제목 링크: Click here~~
제목:
n개의 점의 유방향도를 제시하고 각 점마다 각각 하나의 숫자 p[i]가 있으며 획득한 점수는 지나간 점의 최소 공배수이며 최소 공배수가 변하지 않는 상황이 나타날 수 없다.
처음에는 주인공이 점 1을 찍고 점 n까지 갔을 때 점수가 k인 방안을 물었다.
문제 해결 방법:
단순화된 상태가 필요한 DP
원래의 유방향도는 무환을 보장하지 않지만 최소 공배수가 변하지 않는 상황이 나타날 수 없기 때문에 본 문제는 dp가 될 수 있다. 왜냐하면 갈 수 있는 경로에는 반드시 고리가 나타나지 않기 때문이다.
dp[u][score]로 하여금 점 u에 도달했을 때 점수가 score인 방안수를 표시하고 초기 dp[u][k]=1이다.
dp[u][score]=sum{dp[v][lcm(score, v)]}(∈G&k%lcm=0)가 있다.
그러나 score의 범위가 너무 넓어서 상태수가 너무 많아 풀 수가 없다.사실 score가 k인 인자만 풀 수 있다는 것을 발견하기 어렵지 않다. 즉, 상태가 합법적이라는 것이다.
그러므로 우리는 이 점에 따라 상태를 간소화할 수 있다. 실현 방법은 맵으로 비추고 dp[u][M[score]로 상태를 표시하는 것이다.
그래서 2차원은 인자 개수의 최대치만 열면 된다. 그러나 나는 한 수의 인자 개수가 어떤 등급인지 잊어버렸다. 직접 측정한 결과 100만 원은 256, 10만 원은 128,
역추는 번거롭기 때문에 기억화 검색으로 쓸 수 있어 편리하다.
#include <map>
#include <vector>
#include <stdio.h>
#include <string.h>

using namespace std;

const int N = 2e3 + 5;
const int mod = 1e9 + 7;

typedef long long LL;

inline int gcd(int a,int b){
    return b ? gcd(b,a%b) : a;
}

inline LL lcm(int a,int b){
    return (LL)a / gcd(a,b) * b;
}

int n,k,p[N],dp[N][256];

vector<int> g[N];

map<int,int> M;

int dfs(int u,int score)
{
    int id = M[score];
    if(dp[u][id] != -1)
        return dp[u][id];
    int ret = 0;
    for(int i=0;i<(int)g[u].size();i++){
        int v = g[u][i];
        LL Lcm = lcm(score,p[v]);
        if(k % Lcm || Lcm == score && u != 0)
            continue;
        (ret += dfs(v,Lcm)) %= mod;
    }
    return dp[u][id] = ret;
}

int main()
{
    int m;
    while(~scanf("%d%d%d",&n,&m,&k))
    {
        for(int i=0;i<=n;i++)
            g[i].clear();
        while(m--){
            int u,v;
            scanf("%d%d",&u,&v);
            g[u].push_back(v);
        }
        for(int i=1;i<=n;i++)
            scanf("%d",&p[i]);
        if(k % p[n])
            puts("0");
        else{
            g[0].push_back(1);
            M.clear();
            int id = 0;
            for(int i=1;i*i<=k;i++)
                if(k%i == 0){
                    M[i] = id++;
                    M[k/i] = id++;
                }
            memset(dp,-1,sizeof(dp));
            dp[n][ M[k] ] = 1;
            printf("%d
",dfs(0,1));
        }
    }
    return 0;
}
프로메테우스와 그라파나로 당신의 데이터베이스를 감시하세요
PHP를 위한 정적 분석 SaaS의 주관적 비교(Scrutinizer, SensioLabsInsight, CodeClimate)

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage