动态规划——疯狂的采药

疯狂的采药"/>

动态规划——疯狂的采药

动态规划——疯狂的采药

P1616 疯狂的采药

解题思路

01背包的另一种形式，这里我们只需要将上面的倒序改成正序即可(还是从w[i]截断)

代码实现

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#define rep(i,s,n) for(long long i=s;i<n;i++)
#define reb(i,d,n) for(long long i=n;i>=d;i--)
using namespace std;
const int SIZE = 10000005;
struct data
{long long t;long long m;
};
struct data herb[10001];
long long tt, temp;
long long dp[SIZE];signed main()
{ios::sync_with_stdio(false);memset(dp, 0, sizeof(dp));cin >> tt >> temp;rep(i, 0, temp)cin >> herb[i].t >> herb[i].m;long long now = tt;rep(i, 0, temp){rep(j, herb[i].t, tt + 1){dp[j] = max(dp[j], dp[j - herb[i].t] + herb[i].m);}}cout << dp[tt];return 0;}

注意

1 0 7 10^7 107应该是有7个0

一定要开long long !!!