SGU 116 Index of super-prime

SGU_116
처음에 거슬러 올라가서 썼는데 효율이 여전히 높다는 것을 알았지만 현재 선택한 것이 클수록 반드시 좋은 것은 아니라는 것을 주의해야 한다.
나중에 다른 사람의 문제풀이를 보고 dp의 해법을 언급했다. 그래서 dp로 썼다. f[i]로 i가 최소한 몇 개의 슈퍼소수의 합으로 분해될 수 있음을 표시하고fa[]로 의사결정의 과정을 기록하면 된다.

//  
#include<stdio.h>
#include<string.h>
#define MAXD 10010
#define INF 0x3f3f3f3f
int N, isprime[MAXD], prime[MAXD], p, sprime[MAXD], sp, a[MAXD], ans[MAXD], num;
void prepare()
{
    int i, j, k;
    memset(isprime, -1, sizeof(isprime));
    p = 0;
    for(i = 2; i <= 10000; i ++)
        if(isprime[i])
        {
            prime[++ p] = i;
            for(j = i * i; j <= 10000; j += i)
                isprime[j] = 0;
        }
    sp = 0;
    for(i = 2; i <= p; i ++)
        if(isprime[i])
            sprime[++ sp] = prime[i];
}
void dfs(int t, int cur, int s)
{
    int i, j;
    if(cur >= num)
        return ;
    if(s == 0)
    {
        num = cur;
        for(i = 0; i < cur; i ++)
            ans[i] = a[i];
        return ;
    }
    for(i = t; i > 0; i --)
        if(s >= sprime[i])
        {
            a[cur] = sprime[i];
            dfs(i, cur + 1, s - sprime[i]);
        }
}
void solve()
{
    int i, j ,k;
    num = 0x3f3f3f3f;
    dfs(sp, 0, N);
    if(num == INF)
        printf("0
");
    else
    {
        printf("%d
", num);
        printf("%d", ans[0]);
        for(i = 1; i < num; i ++)
            printf(" %d", ans[i]);
        printf("
");
    }
}
int main()
{
    int i, j, k;
    prepare();
    while(scanf("%d", &N) == 1)
    {
        solve();
    }
    return 0;
}

//dp
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAXD 10010
#define INF 0x3f3f3f3f
int N, isprime[MAXD], prime[MAXD], p, sprime[MAXD], sp, a[MAXD], ans[MAXD], num, f[MAXD], fa[MAXD];
int cmp(const void *_p, const void *_q)
{
    int *p = (int *)_p;
    int *q = (int *)_q;
    return *q - *p;
}
void prepare()
{
    int i, j, k;
    memset(isprime, -1, sizeof(isprime));
    p = 0;
    for(i = 2; i <= 10000; i ++)
        if(isprime[i])
        {
            prime[++ p] = i;
            for(j = i * i; j <= 10000; j += i)
                isprime[j] = 0;
        }
    sp = 0;
    for(i = 2; i <= p; i ++)
        if(isprime[i])
            sprime[++ sp] = prime[i];
    memset(f, 0x3f, sizeof(f));
    f[0] = 0;
    for(i = 1; i <= 10000; i ++)
        for(j = 1; j <= sp && sprime[j] <= i; j ++)
            if(f[i - sprime[j]] + 1 < f[i])
            {
                f[i] = f[i - sprime[j]] + 1;
                fa[i] = i - sprime[j];
            }
}
void solve()
{
    int i, j ,k;
    num = 0x3f3f3f3f;
    if(f[N] == INF)
        printf("0
");
    else
    {
        for(i = N, k = 0; i != 0; i = fa[i])
            ans[k ++] = i - fa[i];
        qsort(ans, k, sizeof(ans[0]), cmp);
        printf("%d
", k);
        printf("%d", ans[0]);
        for(i = 1; i < k; i ++)
            printf(" %d", ans[i]);
        printf("
");
    }
}
int main()
{
    int i, j, k;
    prepare();
    while(scanf("%d", &N) == 1)
    {
        solve();
    }
    return 0;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

vue 리셋 수조의 수정 수조가 index의 값을 지정하는 작업

다음과 같습니다. vm.items[indexOfItem] = newValue vue는 수조의 변동을 검출할 수 없습니다 vue를 사용할 수 있는 set 방법을 실현하려면 this.$set(this.items,inde...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

SGU 116 Index of super-prime

좋은 웹페이지 즐겨찾기