UVA 10163 Storage Keepers

UVA_10163

    这个题目数据范围比较小，所以一开始我写了M*N*logP的程序也能跑过。先说说二分的思路吧，我们可以二分每个仓库的安全值下限，然后去求最小费用。

    后来看了别人的解题报告后发现，可以做两次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\n");
    else
        printf("%d %d\n", 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\n");
        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\n", min, f[M][N]);
}
int main()
{
    while(init())
        solve();
    return 0;
}