301 条题解
-
-2JimmyChen LV 8 @ 2017-07-08 19:48:25
#include <cstdio> #include <iostream> #include <algorithm> #include <cstring> using namespace std; int main(){ int t, m; cin >> t >> m; int time[m + 1]; int value[m + 1]; for (int i = 1; i <= m; i++){ cin >> time[i] >> value[i]; } int dp[m + 1][t + 1]; memset(dp, 0, sizeof(dp)); for (int i = 1; i <= m; i++){ for (int j = 0; j <= t; j++){ if (j - time[i] >= 0) dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - time[i]] + value[i]); else dp[i][j] = dp[i - 1][j]; } } cout << dp[m][t] << endl; return 0; }