网站删除模块,西安做网站公司,双喜常州网站建设,做网站需要什么学历题解
第一次写树上分组背包的题目。
什么是分组背包#xff1f;
分组背包就是将物品进行分组每组内部只能选择一类物品。
for(int i 1;i N;i){for(int j 0;j V;j){for(int k 0;k item[I];k){dp[i][j] max(dp[i][j],dp[i-1][j-v[i][k]]w[i][k]); }}
…题解
第一次写树上分组背包的题目。
什么是分组背包
分组背包就是将物品进行分组每组内部只能选择一类物品。
for(int i 1;i N;i){for(int j 0;j V;j){for(int k 0;k item[I];k){dp[i][j] max(dp[i][j],dp[i-1][j-v[i][k]]w[i][k]); }}
}
//i代表组别
//j代表容量
//k代表组内物品
在本题中的使用
设dp[u][i]dp[u][i]dp[u][i]表示从u出发在u的子树中广播了i个人所获利的最大值。 然后u的一个子树就代表一个分组。 子树中广播1个用户的最大获利、广播2个用户的最大获利、、、都可以看成是平等的item。 为了避免本组内部取到多于一个的Item所以必须使用滚动数组在这里我用的方法是使用临时数组本质是一样的。
//初始化一个空数组作为本次计算的存储变量。
for(int j 1;j szsznow;j)dp[3000][j] -inf;for(int j 0;j szsznow;j){//枚举要广播的个数for(int k 0;k min(j,sznow);k){//在组内枚举改组要广播的个数看成单个物品dp[3000][j] max(dp[3000][j],dp[u][j-k]dp[v][k]-mo);}
}
代码
#include iostream
#include cstdio
#include cstring
#include vector
using namespace std;
const int inf 1e8;
typedef pairint,int pii;
const int maxn 3005;
int n,m;
int dp[maxn][maxn];
int A[maxn],C[maxn],M[maxn];
vectorpii G[maxn];
int dfs(int u){int sz 0;dp[u][0] 0;if(u n-m){dp[u][1] M[u];return 1;}for(int i 0;i G[u].size();i){pii p G[u][i];int v p.first;int mo p.second;int sznow dfs(v);dp[3000][0] 0;for(int j 1;j szsznow;j)dp[3000][j] -inf;for(int j 0;j szsznow;j){for(int k 0;k min(j,sznow);k){dp[3000][j] max(dp[3000][j],dp[u][j-k]dp[v][k]-mo);}}for(int j 0;j szsznow;j)dp[u][j] max(dp[u][j],dp[3000][j]);sz sznow;}return sz;
}
int main(){for(int i 0;i maxn;i)for(int j 0;j maxn;j)dp[i][j] -inf;cinnm;for(int i 1;i n-m;i){int k;scanf(%d,k);for(int j 0;j k;j){scanf(%d%d,A[j],C[j]);G[i].push_back(make_pair(A[j],C[j]));}}for(int i n-m1;i n;i)scanf(%d,M[i]);int sz dfs(1);for(int i sz;i 0;--i){if(dp[1][i] 0)return 0*printf(%d\n,i);}
}
