牛客多校第六场 J

图片说明

题意：
给出n个技能和m个金币，
当你修炼完所有的第m个技能，，就是第m列都修炼完，就能得到第m个位置的金币，修炼技能需要消耗金币，如果是负数，修炼技能就能得到金币。问你最多能得到多少金币。
题解：
最简单易懂的是枚举i作为level最小的技能，然后在j到m之间任取最小值，最好看代码，很好理解，用前缀和解决简单一点。

代码：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll a[1010][1010],b[1010],pre[1010][1010],preb[1010],minpre[1010][1010];
int main()
{
  int t;
  ll n,m;
  scanf("%d",&t);
  for(int cas = 1;cas <= t;cas++)
  {
      ll ans = 0;
      scanf("%lld%lld",&n,&m);
      for(int i=1;i<=n;i++)
      {
          for(int j=1;j<=m;j++){
              scanf("%lld",&a[i][j]);
              pre[i][j] = pre[i][j-1]+a[i][j];
          }
          minpre[i][m+1] = 1e17;
          for(int j=m;j>=0;j--){
              minpre[i][j] = min(pre[i][j],minpre[i][j+1]);
          }
      }
      for(int i=1;i<=m;i++){
          scanf("%lld",&b[i]);
          preb[i] = preb[i-1]+b[i];
      }
      for(int i=0;i<=m;i++)
      {
          ll sum = 0,minn = 1e18;
          int k;
          for(int j=1;j<=n;j++)
          {
              sum += -pre[j][i] + max(pre[j][i] - minpre[j][i] , 0ll);
              minn = min(minn,max(pre[j][i] - minpre[j][i] , 0ll));
          }
          ans = max(ans,preb[i]+sum-minn );
      }
      printf("Case #%d: %lld\n",cas,ans);
  }
  return 0;
}