萌新6：16进制世界（dp）

news/2024/9/19 22:36:28/ 标签: 算法

题目描述

这是一个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

做法

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;}