树形DP，不同的是，只要选择一个根节点i，它的子树中的所有节点也被选择，代价为cost[i]
由于dfs时，先遍历子树，再返回根节点，这样，以i为根的子树中的节点可能被多次利用，解决办法就是访问到i时，先开一个tmp数组当前的状态，即dp值，然后访问子树，返回时，先更新tmp值，再用tmp值更新dp值
还有一个trick就是，题目要求的是至少m张选票，不是刚好m张，所以可以大于m
代码:
- #include<iostream>
- #include<memory.h>
- #include<string>
- #include<cstdio>
- #include<algorithm>
- #include<math.h>
- #include<stack>
- #include<queue>
- #include<vector>
- #include<map>
- using namespace std;
- struct node
- {
- int v,next;
- }g[205*205];
- map<string,int>mp;
- int adj[205],dp[405],cnt[205],e,in[205],cost[205];
- int n,m;
- char s[105];
- void add(int u,int v)
- {
- g[e].v=v; g[e].next=adj[u]; adj[u]=e++;
- }
- void dfs(int u)
- {
- int i,k,v;
- cnt[u]=1;
- int tmp[405];
- memcpy(tmp,dp,sizeof(dp));
- for(i=adj[u];i!=-1;i=g[i].next)
- {
- v=g[i].v;
- dfs(v);
- cnt[u]+=cnt[v];
- }
- for(i=m+cnt[u];i>=cnt[u];i--)
- {
- //k=min(i,m);
- tmp[i]=min(tmp[i],tmp[i-cnt[u]]+cost[u]);
- dp[i]=min(dp[i],tmp[i]);
- }
- }
- int main()
- {
- int i,j,k,l,w,idx;
- char c;
- while(gets(s))
- {
- if(s[0]=='#')
- break;
- sscanf(s,"%d%d",&n,&m);
- mp.clear();
- memset(adj,-1,sizeof(adj));
- memset(in,0,sizeof(in));
- e=idx=0;
- for(i=1;i<=n;i++)
- {
- dp[i]=dp[i+n]=1<<20;
- scanf("%s%d",s,&w);
- k=mp[s];
- if(k==0)
- {
- mp[s]=++idx;
- k=idx;
- }
- cost[k]=w;
- c=getchar();
- while(c==' ')
- {
- scanf("%s",s);
- l=mp[s];
- if(l==0)
- {
- mp[s]=++idx;
- l=idx;
- }
- add(k,l);
- in[l]++;
- c=getchar();
- }
- }
- dp[0]=0;
- for(i=1;i<=n;i++)
- {
- if(in[i]==0)
- dfs(i);
- }
- int ans=1<<20;
- for(i=m;i<=2*n;i++)
- ans=min(dp[i],ans);
- printf("%d\n",ans);
- }
- return 0;
- }