注意》=m就行。
#include <iostream> #include <cstdio> #include <cmath> #include <algorithm> #include <vector> #include <iomanip> #include <cstring> #include <map> #include <queue> #include <set> #include <cassert> #include <stack> #include <bitset> #include <unordered_set> #define mkp make_pair //#define err cout<<"here"<<endl using namespace std; const double EPS=1e-12; typedef long long lon; typedef unsigned long long ull; typedef set<int>::iterator IT; const lon SZ=220,SSZ=120,APB=52,mod=97,one=1; const lon INF=0x7FFFFFFF; int n,m,arr[SZ],in[SZ],dp[SZ][SZ]; struct nd{ int to,wt; nd(int a=0,int b=0):to(a),wt(b){} }; char ch[SZ]; map<string,int> st; int cnt=0,siz[SZ]; vector<int> mp[SZ]; bool read() { for(;cin.peek()==' ';cin.get()); //cout<<(cin.peek()=='\n')<<endl; if(cin.peek()=='\n') { cin.get(); return 0; } int sz=0; for(;cin.peek()!=' '&&cin.peek()!='\n';)ch[sz++]=cin.get(); ch[sz]=0; //cout<<ch<<endl; return 1; } void build(int x) { for(;read();) { string str(ch); if(st.find(str)==st.end())st[str]=++cnt; int id=st[str]; mp[x].push_back(id); ++in[id]; } } void init() { cin>>n>>m; for(int i=0;i<=n;++i)mp[i].clear(); st.clear(),cnt=0; memset(in,0,sizeof(in)); for(int i=1;i<=n;++i) { //cout<<"i: "<<i<<endl; for(;cin.peek()==' '||cin.peek()=='\n';cin.get()); read(); string str(ch); if(st.find(str)==st.end())st[str]=++cnt; int id=st[str]; cin>>arr[id]; build(id); } for(int i=1;i<=cnt;++i) { if(in[i]==0)mp[0].push_back(i); } arr[0]=INF; memset(dp,0x3f,sizeof(dp)); } void dfs(int x) { siz[x]=1; dp[x][0]=0; for(int k=0;k<mp[x].size();++k) { int to=mp[x][k]; dfs(to); siz[x]+=siz[to]; for(int i=siz[x]-1;i>=0;--i) { for(int j=0;j<=i;++j) { dp[x][i]=min(dp[x][i],dp[x][i-j]+dp[to][j]); } //cout<<x<<" "<<i<<" "<<dp[x][i]<<endl; } } dp[x][siz[x]]=arr[x]; } void work() { dfs(0); int res=INF; for(int i=m;i<SZ;++i)res=min(res,dp[0][i]); cout<<res<<endl; } void release() { //memset(dp,0,sizeof(dp)); //memset(num,0,sizeof(num)); } int main() { std::ios::sync_with_stdio(0); //freopen("d:\\1.txt","r",stdin); int casenum; //memset(dst,0x5a,sizeof(dst)); //cout<<dst[0][0]<<endl; //cin>>casenum; //cout<<casenum<<endl; //for(int time=1;time<=casenum;++time) for(int time=1;;++time) { for(;cin.peek()==' '||cin.peek()=='\n';cin.get()); if(cin.peek()=='#')break; init(); work(); release(); } return 0; }