RQNOJ 202 奥运火炬登珠峰：01背包

题目链接：https://www.rqnoj.cn/problem/202

题意：

　　登珠峰需要携带a(L)O₂和t(L)N_2。

　　有n个气缸可供选择。其中第i个气缸能装下a[i](L)O2和t[i](L)N₂，气缸重量为w[i]。

　　问你在满足需求的前提下，最小的气缸总重量为多少。

题解：

　　二重01背包。

　　表示状态：

　　　　dp[i][j][k]表示考虑到第i个气缸（还没选），已经能装下j(L)O₂和k(L)N_2。

　　　　dp[i][j][k] = 此时的最小总重量

　　找出答案：

　　　　min dp[i][j][k]　(j>=a && k>=t)

　　　　（气缸编号为0~n-1）

　　如何转移：

　　　　由于此题与传统背包的区别为：氧气和氮气的容量需要大于等于所需体积。

　　　　所以顺推。

　　　　now: dp[i][j][k]

　　　　dp[i+1][j][k] = max dp[i][j][k]　（不选）

　　　　dp[i+1][j+a[i]][k+t[i]] = max dp[i][j][k] + w[i]

　　注：数据较水，可以不用考虑氧气拿的很少不够需求，而氮气大大超出需求的极端情况。

AC Code:

// state expression:

// dp[i][j][k] = min weight of cylinders

// i: considering ith cylinder

// j: O2

// k: N2

//

// find the answer:

// min dp[n][>O2][>N2]

//

// transferring:

// now: dp[i][j][k]

// dp[i+1][j][k] = min dp[i][j][k]

// dp[i+1][j+co2[i]][k+cn2[i]] = min dp[i][j][k] + w[i]

//

// bound:

// dp[0][0][0] = 0

// others = -1

#include <iostream>

#include <stdio.h>

#include <string.h>

#define MAX_N 2005

#define MAX_O2 50

#define MAX_N2 170

#define INF 10000000

using namespace std;

int n;

int ans;

int o2,n2;

int co2[MAX_N];

int cn2[MAX_N];

int w[MAX_N];

int dp[MAX_N][MAX_O2][MAX_N2];

void read()

{

    cin>>o2>>n2>>n;

    for(int i=;i<n;i++)

    {

        cin>>co2[i]>>cn2[i]>>w[i];

    }

}

void solve()

{

    ans=INF;

    memset(dp,-,sizeof(dp));

    dp[][][]=;

    for(int i=;i<n;i++)

    {

        for(int j=;j<=o2;j++)

        {

            for(int k=;k<=n2;k++)

            {

                if(dp[i][j][k]!=-)

                {

                    if(dp[i+][j][k]==- || dp[i+][j][k]>dp[i][j][k])

                    {

                        dp[i+][j][k]=dp[i][j][k];

                    }

                    if(dp[i+][j+co2[i]][k+cn2[i]]==- || dp[i+][j+co2[i]][k+cn2[i]]>dp[i][j][k]+w[i])

                    {

                        dp[i+][j+co2[i]][k+cn2[i]]=dp[i][j][k]+w[i];

                        if(j+co2[i]>=o2 && k+cn2[i]>=n2) ans=min(ans,dp[i+][j+co2[i]][k+cn2[i]]);

                    }

                    if(j>=o2 && k>=n2) ans=min(ans,dp[i][j][k]);

                }

            }

        }

    }

}

void print()

{

    cout<<ans<<endl;

}

int main()

{

    read();

    solve();

    print();

}

巴特西

RQNOJ 202 奥运火炬登珠峰：01背包

最新文章

热门文章