CF815C Karen and Supermarket

一、题目

点此看题

二、解法

首先可以把树建出来，由于价格范围太大，所以把物品个数加进状态中，设$dp[u][i][0/1]$为$u$为根的子树内，买了$i$件物品，$u$有没有被买（能不能用优惠券）的最小花费，转移相当于一个背包，特别注意能用劵的情况下可以让子树不用劵。

咋一看这样做的时间复杂度是$O(n^3)$的，考虑一种常用的树上复杂度计算方式，由于没对点只会在$lca$处被计算一次，所以时间复杂度是$O(n^2)$的，实现中要特别注意怎么赋初值。

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int M = 5005;
int read()
{
int x=0,flag=1;char c;
while((c=getchar())<'0' || c>'9') if(c=='-') flag=-1;
while(c>='0' && c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x*flag;
}
int n,m,tot,f[M],a[M],b[M],siz[M],dp[M][M][2];
struct edge
{
int v,next;
}e[M];
void dfs(int u)
{
siz[u]=1;
dp[u][0][0]=0;//这个初值必须赋 
dp[u][1][0]=a[u];
dp[u][1][1]=a[u]-b[u];
for(int x=f[u];x;x=e[x].next)
{
int v=e[x].v;
dfs(v);
for(int i=siz[u];i>=0;i--)
for(int j=siz[v];j>=0;j--)
{
dp[u][i+j][1]=min(dp[u][i+j][1],dp[u][i][1]+dp[v][j][1]);
dp[u][i+j][1]=min(dp[u][i+j][1],dp[u][i][1]+dp[v][j][0]);
dp[u][i+j][0]=min(dp[u][i+j][0],dp[u][i][0]+dp[v][j][0]);
}
siz[u]+=siz[v];
}
}
signed main()
{
n=read();m=read();
memset(dp,0x3f,sizeof dp);
for(int i=1;i<=n;i++)
{
a[i]=read();b[i]=read();
if(i>1)
{
int j=read();
e[++tot]=edge{i,f[j]},f[j]=tot;
}
}
dfs(1);
for(int i=n;i>=0;i--)
if(min(dp[1][i][0],dp[1][i][1])<=m)
{
printf("%dn",i);
return 0;
}
}

最后

以上就是凶狠便当为你收集整理的CF815C Karen and Supermarket的全部内容，希望文章能够帮你解决CF815C Karen and Supermarket所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。