这道题还是有点难的拉。。（我太沙茶了。。）
首先可以看成有依赖的背包问题。。
把牙齿和牙龈都看成物品。。牙齿若要被选则放他的牙龈也要被选。。不就是依赖么。。
首先把物品重新排一下位置（我是用dfs的。。看成树的话。。dfs序正好满足要求俄）。。把牙齿都放在它依赖的牙龈的后面。。
再在开头放个虚拟物品。。方便编程。。。
这样不选的话就可以往后跳过那些牙齿。。就可以DP了
有两种做法。。之间的对比还是很有意义的。。
1：沙茶做法（50分）
设DP[pos,have]为从第pos个物品开始，还有have的money最多能选几个。。
则pos可以选或不选。。然后就可以列出方程了。。很好列。。就不写了。。
时间复杂度（money*N）。。注意到真正有用的money只有72000。。那么就要600*72000的空间。。400多MB！！
（我一开始的沙茶做法）。。
2：Best做法（100分）
既然不行就只好优化阿。。
可以发现前面是有浪费的。。因为如果从因为如果DP[pos,have-1]=DP[pos,have]的话。。后一个根本没必要存阿。。
（位置一样。。钱还多一点。。最多能选的反而一样。。丢人不。。存了有X用阿。。）..
所以只需要存what呢？只需要存DP[pos,have-1]<DP[pos,have]的那些have就可以了(也就是选X个的话最少的钱。。因为再少就不够了)。。
那样的have最多有N个。。因为每个最多能选的都不等嘛。。。
故设DP[pos,X]为从pos个开始。。选X个最少的钱。。。
故DP[pos,X]=min(DP[pos+1,X-(pos是牙齿么？1：0)]+pos的价值,DP[pos+不选pos而跳过的][X]);
用记忆化搜索要方便一些。。。
那么就可以一个个X试过去。。直到在总共中选X个的钱大于P。。然后X-1就OK了。。
P.S
一开始我写第一个发现MLE。。我以为空间可能实际用到的不多。。于是开hash。。结果SB掉了。。
看来抓住问题的本质的能力还不够阿。。
要记录和输出路径阿。。有点麻烦的。。
所以动规中一个重要的思想一定要熟记阿。。只保留有用的状态！！！
写了我N久。。郁闷死了。。
Code。。。
#include<iostream>
#include<ctype.h>
#include<string.h>
using namespace std;
//main data
const int maxn=601,inf=~0U>>2;
int N,K,P;
int S[maxn*2],C[maxn*2]={0};
struct edge
{
int t;edge* next;
edge(int tt,edge*nn):t(tt),next(nn){}
}*E[maxn];
void init()
{
cin>>N>>K>>P;
for(int i=1;i<=K;i++)
{
E[0]=new edge(i,E[0]);
cin>>C[i];
}
for(int i=1;i<=N;i++)
{
int f;
cin>>C[i+maxn]>>f;
E[f]=new edge(i+maxn,E[f]);
}
}
int ord[maxn],cnt=0;
int dfs(int t)
{
ord[cnt++]=t;
if(t>maxn) return S[t]=1;
for(edge*i=E[t];i;i=i->next)
S[t] += dfs(i->t);
return ++S[t];
}
//hash
int DP[2*maxn][maxn+1];
bool Ch[2*maxn][maxn+1];
int dp(int pos,int ch)
{           
if(DP[pos][ch]!=0)
return DP[pos][ch];   
if(ch==0)
return 0;
if(pos>=cnt)
return DP[pos][ch]=inf;
int ind=ord[pos];
int a=dp(pos+1,ch-(ind>maxn?1:0) )+C[ind],b=dp(pos+S[ind],ch);     
if(a<b){Ch[pos][ch]=true;DP[pos][ch]=a;}
else{Ch[pos][ch]=false;DP[pos][ch]=b;}
return DP[pos][ch];
}
int main()
{
init();
dfs(0);
memset(DP,0,sizeof(DP));
int i;
for(i=0;i<=N;i++)
if(dp(0,i)>P) break;
i–;
cout<<i<<endl;
if(i==N)
{
cout<<1;
for(int j=2;j<=N;j++)
cout<<" "<<j;
cout<<endl;
return 0;
}
int now=0,m=i;
bool first=true;
while(m)
{
if(Ch[now][m])
{
if(ord[now]>maxn)
{
m–;if(!first)cout<<" ";
cout<<ord[now]-maxn;first=false;
}
now++;
}
else
{
now+=S[ord[now]];
}
}
}