读入比算法难,我怕了.
先将读入:首先把每个国家的名字和价格读入,用map存名字对应的国家编号,后面的附庸国信息一直读到换行符位置,存到一个s[i]里.
接下来处理附庸国:附庸国之间是用空格隔开的,假设当前考虑的国家是i,那么读到空格就把到现在的字符串的父亲设为i,然后i向这个国家连边就好了.
接下啦我们终于建好了这棵树,可以进行树形dp了.
f[u][j]表示在以国家u为根的子树中,得到不少于j张票至少要多少钱
转移类似树形dp,如果在某个孩子v的子树中选k个,那么u的子树中就选j-k个.
$$f[u][j]=min(f[u][j],f[u][j-k]+f[v][k])\ (0\le j\le size[u],0\le k\le size[v],j\ge k)$$
特别地,$f[u][0]=0,f[u][j]=min(f[u][j],c[u])\ (0\le j\le size[u])$,也就是收买这个国家.
时间复杂度确界是$\Theta(\sum_{u=1}^nsize[u]^2)$,上界为$O(n^3)$
/**********/
typedef std::string str;
#define MAXN 211
ll n,m,c[MAXN];
std::map<str,ll>p;
str a[MAXN],s[MAXN],cur;
struct Edge
{
ll v,nxt;
}e[MAXN<<1|1];
ll cnt=0,last[MAXN];
void adde(ll u,ll v)
{
e[++cnt].v=v;
e[cnt].nxt=last[u],last[u]=cnt;
}
ll fa[MAXN],size[MAXN],f[MAXN][MAXN];
void dp(ll u)
{
f[u][0]=0;
size[u]=1;
for(ll i=last[u];i;i=e[i].nxt)
{
ll v=e[i].v;
dp(v);
size[u]+=size[v];
}
for(ll i=last[u];i;i=e[i].nxt)
{
ll v=e[i].v;
for(ll j=size[u];j>=0;--j)
for(ll k=size[v];k;--k)
if(j>=k)umin(f[u][j],f[u][j-k]+f[v][k]);
}
if(u)
{
for(ll j=0;j<=size[u];++j)umin(f[u][j],c[u]);
}
}
int main()
{
while(std::cin>>n>>m)
{
memset(last,0,sizeof last);memset(fa,0,sizeof fa);
cnt=0;
memset(f,0x3f,sizeof f);
p.clear();
for(ll i=1;i<=n;++i)
{
std::cin>>a[i]>>c[i];
p[a[i]]=i;
s[i]="";
char ch=getchar();
if(ch==' ')ch=getchar();
while(ch!='\n'&&ch!='\r')
{
s[i].push_back(ch);ch=getchar();
}
}
for(ll i=1;i<=n;++i)
{
cur="";
for(ll j=0;j<s[i].size();++j)
if(s[i][j]==' ')
{
ll v=p[cur];
fa[v]=i;
adde(i,v);
cur="";
}
else cur.push_back(s[i][j]);
if(cur=="")continue;
ll v=p[cur];
fa[v]=i;
adde(i,v);
}
c[0]=INF;
for(ll i=1;i<=n;++i)
if(!fa[i])adde(0,i);
dp(0);
printf("%lld\n",f[0][m]);
}
return 0;
}
提问:为什么要算出size呢?直接用m来循环第二层为什么会出错?
啊这读入就离谱((
好像写的好是$\mathcal O(n^2)$的,cf上有过这样的题(可是我不会证。。。)
别说 $O(n^2)$,我连 $O(n^3)$ 似乎都不会