90分求助，第五个点没过

P1064 [NOIP2006 提高组] 金明的预算方案

thomaswmy @ 2021-10-23 15:05:19

#include <bits/stdc++.h>
using namespace std;

int n,m,v[1000],p[1000],q[1000],qnum[1000],b[1000][1000];
int dp[10000000]; // dp[i]代表花i块最大值 

int main() {
    scanf("%d %d",&n,&m);
//  if(n==6000 && m==15) {  //只好打表过了 
//      printf("26400");
//      return 0;
//  }
    n/=10;
    for(int i=1;i<=m;i++) {
        scanf("%d%d%d",&v[i],&p[i],&q[i]);
        v[i]/=10;
        if(q[i]==0) b[i][++qnum[i]]=i; //归属主件 
    }

    for(int i=1;i<=m;i++) {
        if(q[i]>0) b[q[i]][++qnum[q[i]]]=i;
    }

//  for(int i=1;i<=m;i++) {
//      printf("%d ",qnum[i]);
//      for(int j=1;j<=qnum[i];j++) {
//          printf("%d ",b[i][j]);
//      }
//      printf("\n");
//  }

    memset(dp,-1,sizeof(dp));

    dp[0]=0;

    for(int i=1;i<=m;i++) {  //枚举物品 
        if(qnum[i]>0) { //判断是否是主件 
            for(int j=n-v[b[i][1]];j>=0;j--) {  //枚举钱
                if(dp[j]!=-1 && j+v[b[i][1]]<=n) {  //判断越界 
                    if(dp[j+v[b[i][1]]]<=dp[j]+v[b[i][1]]*p[b[i][1]]){
                        dp[j+v[b[i][1]]]=dp[j]+v[b[i][1]]*p[b[i][1]];  //买主件 
                        if(qnum[i]>1) {
                            if(j+v[b[i][1]]+v[b[i][2]]<=n) dp[j+v[b[i][1]]+v[b[i][2]]]=max(dp[j+v[b[i][1]]+v[b[i][2]]],dp[j]+v[b[i][1]]*p[b[i][1]]+v[b[i][2]]*p[b[i][2]]);
                            if(qnum[i]>2) {
                                if(j+v[b[i][1]]+v[b[i][3]]<=n) dp[j+v[b[i][1]]+v[b[i][3]]]=max(dp[j+v[b[i][1]]+v[b[i][3]]],dp[j]+v[b[i][1]]*p[b[i][1]]+v[b[i][3]]*p[b[i][3]]);
                                if(j+v[b[i][1]]+v[b[i][2]]+v[b[i][3]]<=n) dp[j+v[b[i][1]]+v[b[i][2]]+v[b[i][3]]]=max(dp[j+v[b[i][1]]+v[b[i][2]]+v[b[i][3]]],dp[j]+v[b[i][1]]*p[b[i][1]]+v[b[i][2]]*p[b[i][2]]+v[b[i][3]]*p[b[i][3]]);
                            }
                        }
//                      for(int k=2;k<=qnum[i];k++) {  //枚举附件 
//                          if(j+v[b[i][1]]+v[b[i][k]]>n) continue;
//                          dp[j+v[b[i][1]]+v[b[i][k]]]=max(dp[j+v[b[i][1]]+v[b[i][k]]],dp[j]+v[b[i][1]]*p[b[i][1]]+v[b[i][k]]*p[b[i][k]]);
//                          for(int l=2;l<=qnum[i];l++) {
//                              if(j+v[b[i][1]]+v[b[i][k]]+v[b[i][l]]>n) continue;
//                              if(l==k) continue;
//                              dp[j+v[b[i][1]]+v[b[i][k]]+v[b[i][l]]]=max(dp[j+v[b[i][1]]+v[b[i][k]]+v[b[i][l]]],dp[j]+v[b[i][1]]*p[b[i][1]]+v[b[i][k]]*p[b[i][k]]+v[b[i][l]]*p[b[i][l]]);
//                          }
//                      }

                    }
                }
            }
        }
    }
    int ans=0;
    for(int i=0;i<=n;i++) {
        ans=max(ans,dp[i]*10);
//      printf("%d %d\n",i,dp[i]);
    }
    printf("%d",ans);
    return 0;
}

这是第五个点：