题解 | #[NOIP2006]金明的预算方案#

import java.io.*;
import java.util.*;
class Item{
    int v0,p0;
    public Item(int v0,int p0) {
	this.v0=v0;this.p0 = p0; 
    }
    int v1,p1;
    int v2,p2;
}
public class Main {
    static PrintWriter out = new PrintWriter(System.out);
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static String next() throws Exception{
    while (st == null || !st.hasMoreTokens())
	st = new StringTokenizer(br.readLine());
	return st.nextToken();
    }
    static int nextInt()throws Exception{
	return Integer.parseInt(next());
    }
    static int m,n;
    static long[] dp;
    public static void main(String[] args) throws Exception {
	 m=nextInt(); n= nextInt(); 
	 Map<Integer,Item> items = new HashMap<>();
	 dp = new long[m+1];
	 //输入
	 for(int i = 1;i<=n;i++) {
	   int a =nextInt(); //价值
	   int b = nextInt();//重要度
	   int c = nextInt();//附属
	   if(c==0) 
	   	items.put(i,new Item(a, b));
	   else {
	   	Item it = items.get(c);
	   	if(it.v1==0) {
	   	    it.v1 = a; it.p1=b;
	   	}else {
	   	    it.v2 =a;it.p2=b;
	   	}
	   }
    }
	items.forEach((a,item)->{
    //主键 a  物品item
	for(int j=m;j>=1;j--) {
	  //1.只用主物品
	  if(j>=item.v0) 
	      dp[j] = Long.max(item.p0*item.v0+dp[j-item.v0],dp[j]);
	  //2.主+1
	  if(item.p1!=0&&j>=(item.v0+item.v1)) 
	    dp[j] = Long.max(dp[j],
		     (item.p0*item.v0)+(item.p1*item.v1)+dp[j-(item.v0+item.v1)]);
	  //3.主+2
	  if(item.p2!=0&&j>=(item.v0+item.v2)) 
		dp[j] = Long.max(dp[j],
		    (item.p0*item.v0)+(item.p2*item.v2)+dp[j-(item.v0+item.v2)]);
	  //4.主+1+2
	  if(item.p2!=0&&j>=(item.v0+item.v1+item.v2)) 
		dp[j] = Long.max(dp[j],
		(item.p0*item.v0)+(item.p1*item.v1)+(item.p2*item.v2)+dp[j-(item.v0+item.v1+item.v2)]);
	  }
	});
	  out.println(dp[m]);
	  out.close();
	 }
}