个人技术分享

算法提高之潜水员

• 核心思想：二维01背包

  • 两个容量v1v2
  • 注意状态计算时j和p可以<各自的v
    • 

•   #include <iostream>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    const int N = 1010,M = 80,K = 22;
    int f[K][M];
    int k,V1,V2;
    
    int main()
    {
        cin>>V1>>V2>>k;
        memset(f,0x3f,sizeof f);
        f[0][0] = 0;
        for(int i=0;i<k;i++)
        {
            int v1,v2,w;
            cin>>v1>>v2>>w;
            for(int j=V1;j>=0;j--)
                for(int p=V2;p>=0;p--)
                    f[j][p] = min(f[j][p] , f[max(0,j-v1)][max(0,p-v2)] + w);
        }
        cout<<f[V1][V2]<<endl;
        return 0;
    }