題目描述
學生在我們USACO的競賽中的得分越多我們越高興。我們試著設計我們的競賽以便人們能盡可能的多得分。
現在要進行一次競賽，總時間T固定，有若干類型可選擇的題目，每種類型題目可選入的數量不限，每種類型題目有一個si(解答此題所得的分數)和ti(解答此題所需的時間)，現要選擇若干題目，使解這些題的總時間在T以內的前提下，所得的總分最大。??
輸入
輸入包括競賽的時間，M(1 <= M <= 10000)和題目類型數目N(1 <= N <= 10000)。
后面的每一行將包括兩個整數來描述一種"題型"。第一個整數說明解決這種題目能得的分數(1 <= points <= 10000)，第二整數說明解決這種題目所需的時間(1 <= minutes <= 10000)。
輸出
單獨的一行，在給定固定時間里得到的最大的分數。
樣例輸入
300 4
100 60
250 120
120 100
35? 20樣例輸出
605思路
動態規劃可以分成四部分
? ? ? ? dp1: 狀態定義
? ? ? ? ? ? ? ? dp[i] 表示時間為i的最大的分數
? ? ? ? dp2: 初始化數據
? ? ? ? ? ? ? ? 數組全部初始化為0
? ? ? ? dp3: 求解算法（狀態轉移方程)
? ? ? ? ? ? ? ?
if (i + v1[j].second <= n) 枚舉時間, 時間+當前題目的時間 <= 規定的時間（滿足條件）dp[i + v1[j].second] = max(dp[i + v1[j].second], dp[i] + v1[j].first);dp[i + v1[j].second] 選擇之后的時間所達到的分數
= max(選擇之后的時間原來所達到的分數, 沒有選擇的時候的分數 + 當前題目的分數)很多dp都是這樣子的模式? ? ? ? dp4: 輸出答案
? ? ? ? ? ? ? ? dp[n]?
Code
#include <bits/stdc++.h>
using namespace std;int n, m;
typedef pair<int, int> Ipair;
vector<Ipair> v1;
void Print(vector<int> dp)
{for (auto& it : dp) cout << it << ' ';cout << endl;
}
int main() {cin >> n >> m;v1.resize(m + 1);for (int i = 1; i <= m; i++) cin >> v1[i].first >> v1[i].second;vector<int> dp(n + 1, 0); // dp數組, dp[i] 表示時間為i的最大分數// dp第二步: 求解for (int i = 0; i <= n; i++){for (int j = 1; j <= m; j++){if (i + v1[j].second <= n)dp[i + v1[j].second] = max(dp[i + v1[j].second], dp[i] + v1[j].first);}//Print(dp);}cout << dp[n];return 0;
}
