[暴力+前缀和]2019牛客暑期多校训练营（第六场）Upgrading Technology

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int amn=1e3+5;
 5 const ll inf=1e18;
 6 ll in,c[amn][amn],d[amn],s[amn],cnt,nowmin,a[amn],ans,need,maxs,minn;
 7 int main(){
 8     int n,m,T;
 9     ios::sync_with_stdio(0);
10     cin>>T;
11     for(int ca=1;ca<=T;ca++){
12         memset(s,0,sizeof s);
13         memset(a,0,sizeof a);
14         cin>>n>>m;
15         for(int i=1;i<=n;i++)c[i][0]=0;
16         for(int i=1;i<=n;i++){
17             for(int j=1;j<=m;j++){
18                 cin>>in;                ///题目输入的代价是正的，利润是负的
19                 c[i][j]=c[i][j-1]-in;   ///建立cost前缀和，同时为了方便处理把代价以负数输入，利润以正数输入
20             }
21         }
22         for(int i=1;i<=m;i++){
23             cin>>d[i];                  ///升到i级的到的利润
24         }
25        d[0]=s[0]=0;
26         for(int j=1;j<=m;j++){
27             s[j]=s[j-1]+d[j];           ///建立升到第j级总收益的前缀和，n个人都升到第j级的利润(题目是n个科技树，本文把科技统称为人)
28             for(int i=1;i<=n;i++){
29                 s[j]+=c[i][j]-c[i][j-1];    ///n个人都升到第j级的总代价加入的到总收益中
30             }
31         }
32         ans=0;
33         for(int j=0;j<=m;j++){          ///枚举当前最小的等级为j，则相当于所有人都已经升到了j级
34             need=0;                     ///还可以增加的收益，就是看每个人还可以在已经升到了j级的基础上还可以再自己升多少级（相当于自己偷偷学习）
35             if(j<m){                    ///要j小于m才判断是否可以增加收益，因为如果j为m就升不了级了
36                 cnt=0;minn=inf;
37             for(int i=1;i<=n;i++){
38                 maxs=0;
39                 for(int k=j+1;k<=m;k++){
40                     if(maxs<c[i][k]-c[i][j]){
41                         maxs=c[i][k]-c[i][j];       ///枚举第i个人，升到第j级后是否还能向后升级到多少使得收益是最大的，这里本来想用st表或线段树维护的，但当时觉得太麻烦万一思路错了就白浪费那么多时间，就先暴力交一发验证下思路，没想到竟然过了
42                     }
43                 }
44                 if(maxs>0){                         ///如果最大收益是正的，则加入到可增加的收益中，同时记录加入的人数和所有加入收益的最小值
45                     need+=maxs;
46                     cnt++;
47                     minn=min(minn,maxs);
48                 }
49             }
50             if(cnt==n)need-=minn;                   ///最多只能有n-1个人的收益加入可增加收益，因为如果n个人都增加，那么他们中的最低等级就不是当前的j了，所以如果n个人都可以继续增加收益，则需要把收益最少的那个人的收益从总的可增加收益中减掉，这样才能获得最大合法的可增加收益
51             }
52             ans=max(s[j]+need,ans);                 ///选一个收益最大的作为答案
53         }
54         printf("Case #%d: %lld\n",ca,ans);
55     }
56 }
57 /***
58 有n个科技，他们能有从1到m的等级，一开始等级都为0，当第i个科技从j-1级升到j级时，要花费cij(可能为正可能为负，花费为负就赚了)，
59 除此之外，如果所有科技的等级都大于等于等级j，则可以得到dj的钱（可能为正可能为负，收益为负就亏了，同时能否获得dj取决于最小的那个科技的等级是否大于等于等级j，这个是本题的关键），
60 要求最大收益，注意如果所有科技都不升级，那么收益为0（可能一升级就亏钱，所以就不升啦~）
61 题目输入的代价是正的，利润是负的，建立cost前缀和，同时为了方便处理把代价以负数输入，利润以正数输入，记录升到i级的到的利润
62 建立升到第j级总收益的前缀和，n个人都升到第j级的利润(题目是n个科技树，本文把科技统称为人)，将n个人都升到第j级的总代价加入的到总收益中
63 接着要枚举当前最小的等级为j，则相当于所有人都已经升到了j级，记录下还可以增加的收益，就是看每个人还可以在已经升到了j级的基础上还可以再自己升多少级（相当于自己偷偷学习），同时要j小于m才判断是否可以增加收益，因为如果j为m就升不了级了，
64 枚举第i个人，升到第j级后是否还能向后升级到多少使得收益是最大的，区间问题，用st表或线段树维护下，但这题暴力枚举也是可以过的，最多只能有n-1个人的收益加入可增加收益，因为如果n个人都增加，那么他们中的最低等级就不是当前的j了，所以如果n个人都可以继续增加收益，则需要把收益最少的那个人的收益从总的可增加收益中减掉，这样才能获得最大合法的可增加收益
65 最后选一个从0到m级中收益最大的作为答案
66 ***/