企业网站制作 厦门,治疗男科一般花费多少钱,51我们一起做网站,微信企业app手机下载安装一、蓝桥OJ 1174小明的背包1 模板题 思路#xff1a; 用二维数组dp判断最大价值#xff0c;i表示物品数量#xff0c;j表示物品体积#xff0c;如果 j V 则无需继续#xff0c; j w 物品还能再增加#xff0c;同样价值也增加#xff0c;否则继承之前的价值 用二维数组dp判断最大价值i表示物品数量j表示物品体积如果 j V 则无需继续 j w 物品还能再增加同样价值也增加否则继承之前的价值在之间找Max最大价值。 #includebits/stdc.h
using namespace std;const int N 1e3 4;
int dp[N][N];int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int n, V; cin n V;for(int i 1; i n; i){int w, v; cin w v;for (int j 1; j V; j){if (j w)dp[i][j] max(dp[i-1][j], dp[i-1][j-w] v);else dp[i][j] dp[i-1][j];}}cout dp[n][V] \n;return 0;
} 优化思路 避免新数据更新为新数据。上面的代码每次j的下标都是从小到大 故可以直接当作一个数组每次更新时从后往前更新。 #includebits/stdc.h
using namespace std;
const int N 1e3 4;
int dp[N];int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int n, V; cin n V;for (int i 1; i n; i){int w, v;cin w v;for (int j V; j w; j--){dp[j] max(dp[j], dp[j-w]v);}}cout dp[V] \n;return 0;
} 二、蓝桥OJ 2223背包与魔法 思路 这道题可以分成三类1.不选 2.选但不用魔法 3.选且用魔法 三种中取最大价值的。 #includebits/stdc.h
using namespace std;const int N 1e45;
int dp[N][2]; // 0的时候表示魔法已用,1表示魔法没用int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int n, m, k; cin n m k;for (int i 1; i n; i){int w, v; cin w v;for (int j m; j 0; --j){if (j w){dp[j][0] max(dp[j][0],dp[j-w][0]v);dp[j][1] max(dp[j][1],dp[j-w][1]v);}if (j w k){dp[j][1] max(dp[j][1], dp[j-w-k][0]2*v);}}}cout max(dp[m][0], dp[m][1]) \n;return 0;
} 三、蓝桥OJ 3741倒水 思路 用一个二维dp数组记录所有满意度之和的最大值dp[i][j]中的i表示1~i个客人j表示 倒水j毫升。 分3种情况是否倒着写要看情况 1.当j a时dp[i][j] dp[i-1][j]e 2.当j a and j c时 dp[i][j] max(dp[i-1][j]e, dp[i-1][j-a]b) 3.当jc时 dp[i][j] max(dp[i-1][j-c]d , max(dp[i-1][j]e, dp[i-1][j-a]b)) 下面的代码第一次写忘记了开long long一定要记住 #includebits/stdc.h
using namespace std;
using ll long long;
const int N 1e3 8;
ll dp[N][N];int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int n, m; cin n m;for (int i 1; i n; i){int a, b, c, d, e;cin a b c d e;for (int j 0; j m; j){if (j a) dp[i][j] dp[i-1][j]e;else if (j a j c) dp[i][j] max(dp[i-1][j]e,dp[i-1][j-a]b);else if (j c) dp[i][j] max(dp[i-1][j-c]d, max(dp[i-1][j]e,dp[i-1][j-a]b));}}cout dp[n][m] \n;return 0;
} 四、蓝桥OJ 3637盗墓分赃2 尽量把数组开大一点不然会有测试点错误。 思路 01背包的变形宝藏的重量即宝藏的价值当宝藏的重量和为奇数一定不能平均的分成两份。后面跟01背包一样 #includebits/stdc.h
using namespace std;
const int N 2e4 8;
int a[N],dp[N];int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int n;cin n;int sum 0;for (int i 1; i n; i){cin a[i];sum a[i];}if (sum1){cout no \n;return 0;}sum sum / 2;for (int i 1; i n; i){for (int j sum; j a[i]; j--){dp[j] max(dp[j],dp[j-a[i]]a[i]);}}string res (dp[sum] sum) ? yes: no;cout res \n;return 0;
} 五、蓝桥OJ 5118小兰的神秘礼物 跟 盗墓分赃 一模一样 #includebits/stdc.h
using namespace std;
const int N 1e3 8;
int x[N], dp[N];int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int V; cin V;//箱子的容量int n; cin n;//收集的小物件总数for (int i 1; i n; i) cin x[i];for (int i 1; i n; i)for (int j V; j x[i]; j--) dp[j] max(dp[j],dp[j-x[i]]x[i]);cout V-dp[V] \n;return 0;
}
