首页 > 代码库 > 采药 水题 dp 01背包问题 luogu1048
采药 水题 dp 01背包问题 luogu1048
最基本的01背包,不需要太多解释,刚学dp的同学可以参见dd大牛的背包九讲,直接度娘“背包九讲”即可搜到
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 5 const int maxn = 1000 + 500; 6 int dp[maxn]; 7 int t, m; 8 int s1, v1; 9 10 int main () { 11 scanf("%d %d", &t, &m); 12 for (int i = 1; i <= m; i++) { 13 scanf("%d %d", &s1, &v1); 14 for (int j = t; j >= s1; j--) { 15 dp[j] = std :: max(dp[j], dp[j - s1] + v1); 16 } 17 } 18 int ans = 0; 19 for (int i = 0; i <= t; i++) ans = std :: max(ans, dp[i]); 20 printf("%d", ans); 21 return 0; 22 }
采药 水题 dp 01背包问题 luogu1048
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。