记录编号	228772	评测结果	AAAAAAAAAA
题目名称	[CTSC 1997]选课	最终得分	100
用户昵称	Magic_Sheep	是否通过	通过
代码语言	C++	运行时间	0.567 s
提交时间	2016-02-19 17:03:42	内存使用	0.79 MiB

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn=500+10;
int n,m;
int brother[maxn],child[maxn],score[maxn];
int opt[maxn][maxn];
bool res[maxn];
void read()
{
    score[0]=0;
    scanf("%d%d",&n,&m);
    score[n+1]=0;
    memset(child,-1,sizeof(child));
    memset(brother,-1,sizeof(brother));
    for(int i=1;i<=n;++i)
    {
        int tmp;
        scanf("%d%d",&tmp,score+i);
        brother[i]=child[tmp];
        child[tmp]=i;
    }
}

int solve(int root,int k)
{
    if(root<0 || k<=0)return 0;
    if(opt[root][k]>=0)return opt[root][k];
    opt[root][k]=solve(brother[root],k);
    for(int i=0;i<k;++i)
    {
        if(opt[root][k]<solve(brother[root],i)+solve(child[root],k-i-1)+score[root])
            opt[root][k]=solve(brother[root],i)+solve(child[root],k-i-1)+score[root];
    }
    return opt[root][k];
}
void path(int r,int k)
{
    int b=brother[r],c=child[r];
    if(b>0 && opt[b][k]==opt[r][k])
    {
        res[r]=0;
        path(b,k);
    }
    else
    {
        for(int i=0;i<k;++i)
            if(opt[r][k]==solve(brother[r],i)+solve(child[r],k-i-1)+score[r])
            {
                res[r]=1;
                path(b,i);
                path(c,k-i-1);
                return;
            }
    }
}
void print()
{
    printf("%d\n",opt[0][m+1]);
    path(0,m+1);
    for(int i=1;i<=n;++i)if(res[i])printf("%d\n",i);
}
int main()
{
    freopen("course.in","r",stdin);
    freopen("course.out","w",stdout);
    read();
    memset(opt,-1,sizeof(opt));
    memset(res,0,sizeof(res));
    solve(0,m+1);
    print();
    return 0;
}