本文主要是介绍萌新6：16进制世界（dp），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目描述
这是一个16进制的世界，比如522的16进制是20A。
在5月22日那天，有人送给Bob一些月饼，每个月饼有饱食度和幸福度两个属性。
现在Bob有nnn个月饼，对于每个月饼iii，饱食度为viv_ivi，幸福度为wiw_iwi。
Bob现在有mmm饱食度，意味着他吃的月饼的饱食度之和不大于mmm。
但是由于Bob身处16进制的世界，他吃的月饼的幸福度之和必须是16的倍数。
请帮Bob算一下他最多吃的月饼的数量。
输入描述:
第一行输入两个整数n, mn,\ mn, m接下来nnn行分别输入vi, wiv_i, \ w_ivi, wi表示第iii个月饼的饱食度和幸福度。输入数据保证1≤n⋅m≤1051 \leq n \cdot m \leq 10^51≤n⋅m≤105, 1≤vi≤1051 \leq v_i \leq 10^51≤vi≤105, 1≤wi≤1091 \leq w_i \leq 10^91≤wi≤109。
输出描述:
一个整数，表示Bob最多能吃的月饼数量
示例1
输入
复制2 5 2 16 3 15
2 5 2 16 3 15
输出
复制1
1
做法
dp[i][j][k]为考虑了前i个月饼，当前的饱食度为j,幸福值为k时选取的月饼个数，这是最先想到的。但是呢，这样会爆空间。我们又看到，要求幸福值为16的倍数，那么我们就去余数就好了，k的那一位不用开那么大。
dp数组递推：从当前位置往前推
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
struct ty{int v,w;
}a[100010];
signed main(){scanf("%lld%lld",&n,&m);for(int i=1;i<=n;i++){scanf("%lld%lld",&a[i].v,&a[i].w);}vector<vector< vector<int> > > dp(n+1,vector< vector<int> >(m+1,vector<int>(16)));//考虑了前i个月饼，当前的饱食度为j,幸福值为k（16以内，取模）的个数for(int i=0;i<=n;i++){//初始化！！！！for(int j=0;j<=m;j++){for(int k=0;k<16;k++){dp[i][j][k]=-0x3f3f3f3f;}}}dp[0][0][0]=0;for(int i=1;i<=n;i++){for(int j=0;j<=m;j++){for(int k=0;k<16;k++){//不选dp[i][j][k]=max(dp[i][j][k],dp[i-1][j][k]);//选if(a[i].v<=j){//从当前位置往前推if(a[i].w%16<=k) dp[i][j][k]=max(dp[i][j][k],dp[i-1][j-a[i].v][k-a[i].w%16]+1);else if(16+k-a[i].w%16<16) dp[i][j][k]=max(dp[i][j][k],dp[i-1][j-a[i].v][16+k-a[i].w%16]+1);}} }}int ans=0;for(int i=1;i<=n;i++){for(int j=0;j<=m;j++){ans=max(dp[i][j][0],ans);}}cout<<ans;}dp数组递推：从当前位置往后推
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
struct ty{int v,w;
}a[100010];
signed main(){scanf("%lld%lld",&n,&m);for(int i=1;i<=n;i++){scanf("%lld%lld",&a[i].v,&a[i].w);}vector<vector< vector<int> > > dp(n+1,vector< vector<int> >(m+1,vector<int>(16)));//考虑了前i个月饼，当前的饱食度为j,幸福值为k（16以内，取模）的个数for(int i=0;i<=n;i++){for(int j=0;j<=m;j++){for(int k=0;k<16;k++){dp[i][j][k]=-0x3f3f3f3f;}}}dp[0][0][0]=0;for(int i=1;i<=n;i++){for(int j=0;j<=m;j++){for(int k=0;k<16;k++){dp[i][j][k]=max(dp[i-1][j][k],dp[i][j][k]);//一定要赋值！！！if(j+a[i].v<=m){//从当前位置往后推//不选dp[i][j+a[i].v][(k+a[i].w%16)%16]=max(dp[i-1][j+a[i].v][(k+a[i].w%16)%16],dp[i][j+a[i].v][(k+a[i].w%16)%16]);//选dp[i][j+a[i].v][(k+a[i].w%16)%16]=max(dp[i-1][j][k]+1,dp[i][j+a[i].v][(k+a[i].w%16)%16]);}} }}int ans=0;for(int i=1;i<=n;i++){for(int j=0;j<=m;j++){ans=max(dp[i][j][0],ans);}}cout<<ans;}WA的原因
1.dp数组没有初始化为负数。之前写的一些dp题，求最大值都不用初始化dp数组，因为本身就为0，所以就理所当然了。
2.每层都要赋好值（第二种方法）。要考虑到选和不选的情况，特别是不选的情况。
这篇关于萌新6：16进制世界（dp）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
