P1567 Buyer - 题解

登录注册上岸

以下题解仅供学习参考使用。

抄袭、复制题解，以达到刷AC率/AC数量或其他目的的行为，在N诺是严格禁止的。

N诺非常重视学术诚信。此类行为将会导致您成为作弊者。具体细则请查看N诺社区规则。

2023年8月6日 19:52

dp数组O(n)终极优化版+vector动态更新路径（内存254kb，

P1567

回复 0 | 赞 0 | 浏览 784

#include<iostream> #include<vector> using namespace std; int main() { int M, N; while (cin >> M >> N) { int dp[101] = {0}, w, v; vector<int> path[1001];//动态更新路径 for (int i = 1; i <= N; i++) { cin >> w >> v; for (int j = M; j &...

2023年8月6日 10:36

Buyer 题解：dp数组空间优化，大部分数据都是对的，求各位大佬帮忙

P1567

回复 8 | 赞 0 | 浏览 1.0k

#include<iostream> #include<cstring> using namespace std; int main() { //dp表示背包数组，w是物品的钱数数组，v是物品受欢迎程度数组 //M是可支配钱数，N是物品数，c是保存物品是否被拿的数组 int dp[101], w[1001], v[1001], M, N, c[1001]; while (cin >> M >> N) { memset(dp, 0, sizeof(dp)); memset(c, 0, sizeof(c));//...

2022年7月10日 14:41

最大受欢迎程度及采购方案均可以利用动态规划求解

P1567

回复 0 | 赞 3 | 浏览 5.6k

#include<iostream> #include<cstring> #include<vector> using namespace std; // 可以支配的钱数、清单上可选择的物品种类、输入物品的价格、输入物品的受欢迎程度、状态转移表 int M, N, v[1005], p[1005], dp[1005][105] = {0}; int main() { while (~scanf("%d%d", &M, &N)) { vector<int> buy[105]; // 每个受欢...

2021年2月21日 13:37

通过dp表倒推选择的物品

P1567

回复 0 | 赞 0 | 浏览 9.1k

/* * Description: Buyer (http://noobdream.com/DreamJudge/Issue/page/1567/) * Author: 鱼翔浅底 * Date: 2021-02-21 12:28:18 */ #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <stack> using namespace std; #define m...

2021年2月20日 14:29

01背包记录物品注意一个都放不开的特殊情况

P1567

回复 0 | 赞 0 | 浏览 7.0k

#include <iostream> #include <algorithm> #include <string.h> #include <vector> using namespace std; const int maxn = 1005; int n,m; int v[maxn];//体积 ---价钱 int w[maxn];//价值 ---受欢迎程度 int f[maxn]; int main(){ while(scanf("%...

2021年1月28日 12:09

P1567

回复 0 | 赞 1 | 浏览 9.8k

这道题多了求路径路径和求欢迎度的思想差不多，就是用前一个路径的状态推后一个路径的状态只需考虑能放进去且最优情况时，路径才会发生变化。路径变化在上一个基础上变化。 #include <bits/stdc++.h> using namespace std; const int maxn=1000+5; int a[maxn][maxn]; int w[maxn][maxn]; int main() { memset(a,0,sizeof(a)); int m,n; while(cin>>m>>n) { ...

2020年5月29日 11:36

路径还原，在dp时直接存储最优路径即可

P1567

回复 0 | 赞 0 | 浏览 10.3k

#define ll long long #define vec vector<int> #define inf 0x3f3f3f3f #define MAX 1005 #define P pair<int,int> #define MOD 1000000 int main() { int n, m, w[MAX], v[MAX], dp[MAX]; while (cin >> m >> n) { memset(dp, 0, sizeof(dp)); vec ve[MAX]; ...

2020年3月14日 19:57

111

P1567

回复 0 | 赞 0 | 浏览 8.6k

#include<bits/stdc++.h> using namespace std; int main() { int s,n; while(cin>>s>>n) { int a[1001][101]={0}; int w[1001]={0},v[1001]={0}; int c[101]={0}; int k=1; for(int i=1;i<=n;i++) { cin>>w[i]>>v[i];...

题目Buyer

题解数量8

热门题解

1 最大受欢迎程度及采购方案均可以利用动态规划求解

2 简单思路

3 Buyer 题解：dp数组空间优化，大部分数据都是对的，求各位大佬帮忙找找茬

4 dp数组O(n)终极优化版+vector动态更新路径（内存254kb，运行时间4ms）

5 路径还原，在dp时直接存储最优路径即可

6 111

7 01背包记录物品注意一个都放不开的特殊情况

8 通过dp表倒推选择的物品