2019牛客暑期多校训练营(第六场)J Upgrading Technology

题意：

就是给你n个技能，每个技能最高升到m级，每升一级就是耗费Cij钱，这个Cij可能是负的，如果所有技能都升到或者说超过j等级，就会获得Dj钱，这个Dj也有可能是负值，让你求你最多得到多少钱（技能没有固定说要升到多少级，你也可以不升，这样就获得了0）

题解：

把所以获取的钱都变成正值，耗费的钱转化成负值，只需要处理一下Cij即可

之后计算最大后缀sum[i][j]代表第i个技能，从j+1---m级最大能获得多少钱

1 for(int i=1;i<=n;++i)

2         {

3             sum[i][m]=0;

4             for(int j=m-1;j>=0;j--)

5             {

6                 sum[i][j]=max(0ll,sum[i][j+1]+a[i][j+1]);

7             }

8         }

之后再算一下假设所有技能都是j级是能获得的钱，然后再找n个技能的最大后缀，所有加到一起，还要再后缀里面找到最小的那个，要减去它

因为如果所以后缀都是正值，那么相当于所有技能都升了一级，如果这个时候Dj是负值，而且这个负值还不小，那我们求出来的就不是最小值了

代码：

 1 #include<stdio.h>

 2 #include<string.h>

 3 #include<iostream>

 4 #include<algorithm>

 5 using namespace std;

 6 typedef long long ll;

 7 const int maxn=1005;

 8 const int mod = 998244353;

 9 ll sum[maxn][maxn];

10 int d[maxn],a[maxn][maxn];

11 int main()

12 {

13     int cnt=1,t,n,m;

14     scanf("%d",&t);

15     while(t--)

16     {

17         scanf("%d %d",&n,&m);

18         for(int i=1;i<=n;++i)

19             for(int j=1;j<=m;++j)

20                 scanf("%d",&a[i][j]),a[i][j]=-a[i][j];

21         for(int i=1;i<=m;++i)

22             scanf("%d",&d[i]);  //有可能为负值

23         for(int i=1;i<=n;++i)

24         {

25             sum[i][m]=0;

26             for(int j=m-1;j>=0;j--)

27             {

28                 sum[i][j]=max(0ll,sum[i][j+1]+a[i][j+1]);

29             }

30         }

31         ll now=0,ans=0;

32         for(int j=0;j<=m;++j)

33         {

34             for(int i=1;i<=n;++i)

35                 now+=a[i][j];

36             now+=d[j];

37             ll temp=0,minn=1e18;

38             for(int i=1;i<=n;++i)

39                 temp+=sum[i][j],minn=min(minn,sum[i][j]);

40             ans=max(ans,temp-minn+now);

41         }

42         printf("Case #%d: %lld\n",cnt++,ans);

43     }

44     return 0;

45 }

巴特西

2019牛客暑期多校训练营(第六场)J Upgrading Technology

最新文章

热门文章