UVA 10163 Storage Keepers

UVA_10163
이 문제는 데이터 범위가 비교적 작기 때문에 처음에 내가 M*N*logP를 쓴 프로그램도 뛰어넘을 수 있다.먼저 2분의 1의 사고방식을 말해 보자. 우리는 각 창고의 안전치 하한선을 2분의 1로 나누고 최소 비용을 구할 수 있다.
나중에 다른 사람의 문제풀이 보고서를 본 후에 두 번 dp를 할 수 있다는 것을 발견했다. 첫 번째 dp는 가장 큰 안전치 하한선을 구하고 두 번째 dp는 이 하한선에 따라 가장 작은 비용을 구할 수 있다.

#include<stdio.h>
#include<string.h>
#define MAXN 110
#define MAXM 40
#define INF 0x3f3f3f3f
int N, M, P, f[MAXM][MAXN], p[MAXM];
int init()
{
    int i, j;
    scanf("%d%d", &N, &M);
    if(!N && !M)
        return 0;
    P = 0;
    for(i = 1; i <= M; i ++)
    {
        scanf("%d", &p[i]);
        if(p[i] > P)
            P = p[i];
    }
    return 1;
}
void solve()
{
    int i, j, k, min, mid, max;
    min = 0, max = P + 1;
    for(;;)
    {
        mid = (min + max) / 2;
        for(i = 1; i <= N; i ++)
            f[0][i] = INF;
        for(i = 0; i <= M; i ++)
            f[i][0] = 0;
        for(i = 1; i <= M; i ++)
            for(j = 1; j <= N; j ++)
            {
                f[i][j] = f[i - 1][j];
                for(k = 0; k < j; k ++)
                    if(p[i] / (j - k) >= mid && f[i - 1][k] + p[i] < f[i][j])
                        f[i][j] = f[i - 1][k] + p[i];
            }
        if(min == mid)
            break;
        if(f[M][N] == INF)
            max = mid;
        else
            min = mid;
    }
    if(min == 0)
        printf("0 0
");
    else
        printf("%d %d
", mid, f[M][N]);
}
int main()
{
    while(init())
        solve();
    return 0;
}

#include<stdio.h>
#include<string.h>
#define MAXM 40
#define MAXN 110
#define INF 0x3f3f3f3f
int N, M, f[MAXM][MAXN],p[MAXM];
int init()
{
    int i, j;
    scanf("%d%d", &N, &M);
    if(!N && !M)
        return 0;
    for(i = 1; i <= M; i ++)
        scanf("%d", &p[i]);
    return 1;
}
void solve()
{
    int i, j, k, min, t;
    for(i = 0; i <= M; i ++)
        f[i][0] = INF;
    for(i = 1; i <= N; i ++)
        f[0][i] = 0;
    for(i = 1; i <= M; i ++)
        for(j = 1; j <= N; j ++)
        {
            f[i][j] = f[i - 1][j];
            for(k = 0; k < j; k ++)
            {
                t = f[i - 1][k] < p[i] / (j - k) ? f[i - 1][k] : p[i] / (j - k);
                if(t > f[i][j])
                    f[i][j] = t;
            }
        }
    if(f[M][N] == 0)
    {
        printf("0 0
");
        return ;
    }
    else
        min = f[M][N];
    for(i = 0; i <= M; i ++)
        f[i][0] = 0;
    for(i = 1; i <= N; i ++)
        f[0][i] = INF;
    for(i = 1; i <= M; i ++)
        for(j = 1; j <= N; j ++)
        {
            f[i][j] = f[i - 1][j];
            for(k = 0; k < j; k ++)
                if(p[i] / (j - k) >= min && f[i - 1][k] + p[i] < f[i][j])
                    f[i][j] = f[i - 1][k] + p[i];
        }
    printf("%d %d
", min, f[M][N]);
}
int main()
{
    while(init())
        solve();
    return 0;
}

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

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

ORA-01691 해결 방법

최근 정시 작업표의 데이터는 xml 파일이 너무 커서 제때에 정리하지 못했기 때문에 MDM 압축 파일 피드백에서 상기 오류가 발생하여 이해하지 못했다. 나중에 물어본 후에 데이터베이스 테이블 공간이 부족하다는 것을 ...

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

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

UVA 10163 Storage Keepers

좋은 웹페이지 즐겨찾기