终于AC了，不过希望有人能对我的代码提出改进建议

不妨看看我花了一小时脑子一抽写的离谱代码：

// Problem: P1064 [NOIP2006 提高组] 金明的预算方案
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1064
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
#define MA 1000010

int n,m,u[MA],p[MA],cnt,c,dp[MA];
int uu[MA],pp[MA];

vector<int> v[MA]; //第i个有哪些附属
vector<int> mas;    //不是附属的有哪些

int f[1000][1000];//分组背包，第i组有哪些下标
int b[MA]; //第i组有几个物品

int main(){
    scanf("%d%d",&n,&m);
    for(int i = 1;i<=m;i++){
        int k;
        scanf("%d%d%d",&u[i],&p[i],&k);
        if(k!=0)v[k].push_back(i);//第k个的附属加上这个
        else mas.push_back(i);//不是附属的加一个
    }
    for(int i = 0;i<mas.size();i++){
        //mas[i]为当前不是附属的
        int mu = u[mas[i]],mp = p[mas[i]];
        if(v[mas[i]].size()==0){
            //一个服书也没有
            uu[++cnt] = mu;
            pp[cnt] = mp*mu;

            c++; //c为组下标
            b[c] = 1; //第c组数量
            f[c][b[c]] = cnt;
        }
        else if(v[mas[i]].size()==1){
            //一个附属
            uu[++cnt] = mu;
            pp[cnt] = mp*mu;

            c++; //c为组下标
            b[c] = 1; //第c组数量
            f[c][b[c]] = cnt;

            int v1 = v[mas[i]][0];//第一个附属的下标
            uu[++cnt] = mu+u[v1];
            pp[cnt] = mp*mu+p[v1]*u[v1];
            //c++; //c为组下标
            b[c] = 2; //第c组数量
            f[c][b[c]] = cnt;
        }
        else if(v[mas[i]].size()==2){
            //两个附属
            uu[++cnt] = mu;
            pp[cnt] = mp*mu;

            c++; //c为组下标
            b[c] = 1; //第c组数量
            f[c][b[c]] = cnt;

            int v1 = v[mas[i]][0];//第一个附属的下标
            uu[++cnt] = mu+u[v1];
            pp[cnt] = mp*mu+p[v1]*u[v1];

            //c++; //c为组下标
            b[c] = 2; //第c组数量
            f[c][b[c]] = cnt;

            int v2 = v[mas[i]][1]; //第二个附属的下标（反正最多两个）
            uu[++cnt] = mu+u[v2];
            pp[cnt] = mp*mu+p[v2]*u[v2];

            //c++; //c为组下标
            b[c] = 3; //第c组数量
            f[c][b[c]] = cnt;

            uu[++cnt] = mu+u[v1]+u[v2];
            pp[cnt] = mp*mu+p[v1]*u[v1]+p[v2]*u[v2];

            //c++; //c为组下标
            b[c]=4; //第c组数量
            f[c][b[c]] = cnt;
        }
    }
    /*
    for(int i = 1;i<=c;i++){
        for(int j = 1;j<=b[i];j++){
            printf("%d %d %d\n",f[i][j],uu[f[i][j]],pp[f[i][j]]);
        }
        printf("----------\n");
    }*/
    for(int i = 1;i<=c;i++){
        for(int j = n;j>=0;j--){
            for(int k = 1;k<=b[i];k++){
                int now = f[i][k];
                //printf("%d %d %d\n",now,uu[now],pp[now]);

                if(j>=uu[now]){
                    //printf(":%d %d --> ",dp[j],dp[j-uu[now]]+pp[now]);
                    dp[j] = max(dp[j],dp[j-uu[now]]+pp[now]);
                    //printf("%d\n",dp[j]);
                }

            }
        }
    }
    printf("%d",dp[n]);
    return 0;
}

分组过程不知道能不能再优化一下，太恶心了