[CodeForces815C] Karen and Supermarket[CodeForces212E] IT Restaurants 树形背包模板两道

81 阅读 0 评论 54 点赞

我是靠谱客的博主孤独纸鹤，最近开发中收集的这篇文章主要介绍[CodeForces815C] Karen and Supermarket[CodeForces212E] IT Restaurants 树形背包模板两道，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

传送：815C

212E

树形背包的本质就是树形dp，但是dp的时候考虑是否取某个子树当前状态，取法和一维背包类似。

T1：不难发现一个性质，我们取到两种颜色和一定为N-1。那么树形背包带进来，flag记录答案是否合法。

T2：这题相对模板一点，DP开到三维，多出来的一维表示这个状态是否已经用了优惠券。

今天的博客好捞啊。

T1代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 5005
using namespace std;
inline void read(int &x){
x=0;int f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
x*=f;
}
struct node{
int nex,to;
}edge[maxn<<1];
int head[maxn],tot;
bool flag[maxn];
int N;
inline void insert(int from,int to){
edge[++tot].nex=head[from];
head[from]=tot;
edge[tot].to=to;
}
int siz[maxn],dp[maxn][maxn];
void dfs(int x,int u){
siz[x]=1;
dp[x][0]=1;
for(int i=head[x];i;i=edge[i].nex)
if(edge[i].to^u)
{
dfs(edge[i].to,x);
siz[x]+=siz[edge[i].to];
for(int k=N-1;k>=0;k--)
if(dp[x][k])
dp[x][k+siz[edge[i].to]]=1;
}
int high=N-siz[x];
for(int i=N-1;i>=0;i--)
if(dp[x][i])
dp[x][i+high]=1;
for(int i=1;i<N-1;i++)
if(dp[x][i])
flag[i]=1;
}
int main(){
read(N);
int u,v;
for(int i=1;i<N;i++){
read(u);read(v);
insert(u,v);
insert(v,u);
}
dfs(1,1);
int ans=0;
for(int i=1;i<N-1;i++)
if(flag[i])
ans++;
cout<<ans<<endl;
for(int i=1;i<N-1;i++)
if(flag[i])
cout<<i<<" "<<N-i-1<<endl;
}

View Code

T2代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 5005
using namespace std;
inline void read(int &x){
x=0;int f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
x*=f;
}
struct node{
int nex,to;
}edge[maxn<<1];
int head[maxn],tot;
int N,B;
inline void insert(int from,int to){
edge[++tot].nex=head[from];
head[from]=tot;
edge[tot].to=to;
}
int c[maxn],d[maxn];
int dp[2][maxn][maxn],siz[maxn];
void dfs(int x)
{
dp[0][x][0]=0;
dp[0][x][1]=c[x];
dp[1][x][1]=c[x]-d[x];
siz[x]=1;
for(int i=head[x];i;i=edge[i].nex)
{
dfs(edge[i].to);
for(int j=siz[x];j>=0;j--)
for(int k=0;k<=siz[edge[i].to];k++)
{
dp[0][x][j+k]=min(dp[0][x][j+k],dp[0][x][j]+dp[0][edge[i].to][k]);
dp[1][x][j+k]=min(dp[1][x][j+k],dp[1][x][j]+dp[1][edge[i].to][k]);
dp[1][x][j+k]=min(dp[1][x][j+k],dp[1][x][j]+dp[0][edge[i].to][k]);
}
siz[x]+=siz[edge[i].to];
}
}
int main()
{
memset(dp,0x3f,sizeof(dp));
read(N);read(B);
read(c[1]);read(d[1]);
int u;
for(int i=2;i<=N;i++)
{
read(c[i]);read(d[i]);
read(u);
insert(u,i);
}
dfs(1);
int ans=N;
while(dp[0][1][ans]>B&&dp[1][1][ans]>B)
ans--;
cout<<ans;
}