最大开支（优先队列+贪心）

我的bfs（超时了捏）

 1 import java.util.*;
 2 
 3 import javax.swing.plaf.basic.BasicInternalFrameTitlePane.MaximizeAction;
 4 
 5 public class Demo1 {
 6     static int m;
 7     static int n;
 8     static long sum;
 9     public static void main(String[] args) {
10         Scanner scan=new Scanner(System.in);
11         n=scan.nextInt();
12         m=scan.nextInt();
13         int [][]h=new int[m][2];
14         for(int i=0;i<m;i++) {
15             h[i][0]=scan.nextInt();
16             h[i][1]=scan.nextInt();
17         }
18         BFS(1,0,0,h);
19         scan.close();
20         System.out.println(sum);
21     }
22     public static void BFS(int start,int level,int s,int [][]h) {
23         if(level==m||start>n) {
24             if(s>sum) {
25                 sum=s;
26             }
27             return ;
28         }else {
29             for(int i=start;i<=n;i++) {
30                 int t=(h[level][0]*(i-start+1)+h[level][1])*(i-start+1);
31                 int temp=Max(t,0);
32                 s+=temp;
33                 BFS(i+1,level+1,s,h);
34                 s-=temp;
35             }
36         }
37     }
38     public static int Max(int t,int w) {
39         if(t>w) {
40             return t;
41         }else {
42             return w;
43         }
44     }
45 
46 }

 后来可以考虑增量，所有活动买第一张增量都是k*1+b，然后买下一张就是(k*(x)+b)*x-(k*(x-1)+b)*(x-1),然后对这些增量都排个序，一直选最大的就可以了！！！（秒秒秒）

 1 import java.util.ArrayList;
 2 import java.util.Arrays;
 3 import java.util.Collection;
 4 import java.util.Collections;
 5 import java.util.Comparator;
 6 import java.util.Iterator;
 7 import java.util.List;
 8 import java.util.Scanner;
 9 
10 public class Main {
11     public static  void main(String[] args) {
12         Scanner sc=new Scanner(System.in);
13         int N=sc.nextInt();
14         int M=sc.nextInt();
15         List<Integer> a=new ArrayList<>();
16         for (int i = 1; i <= M; i++) {
17             int k=sc.nextInt();
18             int b=sc.nextInt();
19             for (int j = 1; j <= N; j++) {
20                 int count=(k*j+b)*j-(k*(j-1)+b)*(j-1);
21                 if (count>0) {
22                     a.add(count);
23                 }else {
24                     break;
25                 }
26             }
27         }
28         Collections.sort(a, (o1,o2)-> o2-o1);
29 //           Collections.sort(a, new Comparator<Integer>() {
30 //                @Override
31 //                public int compare(Integer o1, Integer o2) {
32 //                    return o2-o1;
33 //                }
34 //            });
35         long max =0;
36         int choose=Math.min(N, a.size());
37         for (int i = 0; i < choose; i++) {
38             max+=a.get(i);
39         }
40         System.out.println(max);
41     }
42 }