POI 1998 Frogman, SPOJ 181 Scuba diver Summary

March 31, 2009 — gnarlycow

动态规划

本题中的物品涉及两个价值，属于背包问题的简单变形，氧气和氮气各占一维即可。和普通的一维背包问题一样，这里可以通过调整状态转移的顺序来实现空间降维。

?View Code CPP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

#include <cstdio>
#include <cstring>
 
int f[80][80];
 
int main()
{
    int m,n,a,b,w,num,T;
    for(scanf("%d",&T);T;--T)
    {
        memset(f,-1,sizeof(f));
        f[0][0]=0;
        scanf("%d%d%d",&m,&n,&num);
        for(int k=0;k<num;++k)
        {
            scanf("%d%d%d",&a,&b,&w);
            for(int i=79;i>=a;--i)
                for(int j=79;j>=b;--j)
                    if(f[i-a][j-b]>-1&&(f[i][j]==-1||f[i][j]>f[i-a][j-b]+w))
                        f[i][j]=f[i-a][j-b]+w;
        }
        int ans=-1;
        for(int i=m;i<80;++i)
            for(int j=n;j<80;++j)
                if(f[i][j]>-1&&(ans==-1||ans>f[i][j]))
                    ans=f[i][j];
        printf("%d\n",ans);
    }
    return 0;
}
Posted in SPOJ. Tags: , , . No Comments »
«
»