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

ゝ一世哀愁。 2023-10-11 09:33 1阅读 0赞

[传送门][Link 1]

题意：

就是给你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是负值，而且这个负值还不小，那我们求出来的就不是最小值了

代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

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 }

转载于:https://www.cnblogs.com/kongbursi-2292702937/p/11307238.html

[Link 1]: https://ac.nowcoder.com/acm/contest/886/J
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: https://images.cnblogs.com/OutliningIndicators/ExpandedBlockStart.gif