P1616瘋狂的採藥 完全背包

題目背景

此題為紀念 LiYuxiang 而生。

題目描述

LiYuxiang 是個天資聰穎的孩子,他的夢想是成為世界上最偉大的醫師。為此,他想拜附近最有威望的醫師為師。醫師為了判斷他的資質,給他出了一個難題。醫師把他帶到一個到處都是草藥的山洞裡對他說:「孩子,這個山洞裡有一些不同種類的草藥,采每一種都需要一些時間,每一種也有它自身的價值。我會給你一段時間,在這段時間裡,你可以採到一些草藥。如果你是一個聰明的孩子,你應該可以讓採到的草藥的總價值最大。」

如果你是 LiYuxiang,你能完成這個任務嗎?

此題和原題的不同點:

11. 每種草藥可以無限制地瘋狂採摘。

22. 葯的種類眼花繚亂,採藥時間好長好長啊!師傅等得菊花都謝了!

輸入格式

輸入第一行有兩個整數,分別代表總共能夠用來採藥的時間 tt 和代表山洞裡的草藥的數目 mm。

第 22 到第 (m + 1)(m+1) 行,每行兩個整數,第 (i + 1)(i+1) 行的整數 a_i, b_iai,bi 分別表示採摘第 ii 種草藥的時間和該草藥的價值。

輸出格式

輸出一行,這一行只包含一個整數,表示在規定的時間內,可以採到的草藥的最大總價值。

輸入輸出樣例

輸入 #1

70 3
71 100
69 1
1 2
輸出 #1

140

說明/提示

數據規模與約定

  • 對於 30\%30% 的數據,保證 m \le 10^3m103 。
  • 對於 100\%100% 的數據,保證 1 \leq m \le 10^41m104,1 \leq t \leq 10^71t107,且 m \times t < 10^7m×t<107,1 \leq a_i, b_i \leq 10^41ai,bi104。

數據範圍比較大,考慮用一維滾動數組,因為是完全背包,所以權值j順序循環即可。

#include <iostream>
#include <algorithm>
#define maxn 10000 + 5

using namespace std;
int w[maxn], c[maxn];
int dp[10000000 + 5];
int main()
{
    int t, m;
    cin >> t >> m;
    for (int i = 1; i <= m; i++)
    {
        cin >> w[i] >> c[i];
    }
    for (int i = 1; i <= m; i++)
    {
        for (int j = w[i]; j <= t; j++)
        {
            dp[j] = max(dp[j], dp[j – w[i]] + c[i]);
        }
    }
    cout << dp[t] << endl;
}

 

Tags: