专栏首页wym2019牛客暑期多校训练营(第六场)J Upgrading Technology 后缀和

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

题意:有i个技能,每次升级都有花费cij,然后所有技能都达到j级送dj块钱,问你最多能赚多少

解:先将花费乘-1转换为收益,对 a[i][j] 维护后缀和,表示 j+1~m 最大收益。

然后 j 从1 到 m 遍历,j 表示当前某个技能的最低等级,找到 第 i 个技能 最小的后缀和,减去这个后缀和并加上其他技能的后缀和,再加上所以技能都达到 j 的收益取最大值。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll sum[1005][1005];
int d[1005];
int a[1005][1005];
int main() {
	int cnt=1,t,n,m;
	scanf("%d",&t);
	while(t--) {
		scanf("%d %d",&n,&m);
		for(int i=1; i<=n; i++)
			for(int j=1; j<=m; j++)scanf("%d",&a[i][j]),a[i][j]=-a[i][j];
		for(int i=1; i<=m; i++)scanf("%d",&d[i]);
		
		for(int i=1;i<=n;i++){
			sum[i][m] = 0;
			for(int j=m-1;j>=0;j--){
				sum[i][j] = max(0ll,sum[i][j+1]+a[i][j+1]);
			}
		}
		ll now = 0,ans = 0;
		for(int j=0;j<=m;j++){
			for(int i=1;i<=n;i++)now+=a[i][j];
			now+=d[j];
			ll tp = 0,mi = 1e18;
			for(int i=1;i<=n;i++)tp+=sum[i][j],mi = min(mi,sum[i][j]);
			ans = max(ans,tp-mi+now);
		}
		printf("Case #%d: %lld\n",cnt++,ans);
	}
	return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 陕西师范大学第七届程序设计竞赛网络同步赛 排队排队排队

    用户2965768
  • 种树 差分约束|贪心

    每次种的树在重叠区间越多,种的树越少。只有结束位置才会重合,就对区间结束的位置从小到大排序。

    用户2965768
  • [USACO06JAN]牛的舞会 Tarjan模版

    用户2965768
  • 感知机对偶形式C++实现

    下面直接上代码,此处我用的是C++代码用STL中的向量实现存储,当然也可以用数组或者其他方式,感知机的对偶形式代码如下:

    SL_World
  • [每日一题]定义和调用函数fact(k)计算k的阶乘

    在C语言的学习过程中,其实最好的提升能力的方式就是刷题,能够在题海中正真锻炼自己的逻辑思维能力和动手能力,所以先来看看下面这题陶冶陶冶情操。 题目描述 编写程...

    编程范 源代码公司
  • P2709 小B的询问

    题目描述 小B有一个序列,包含N个1~K之间的整数。他一共有M个询问,每个询问给定一个区间[L..R],求 的值,其中i的值从1到K,其中c(i)表示数字i在...

    attack
  • 【CodeForces 618B】Guess the Permutation

    有个1到n的一个全排列,告诉你第i个数和全部n个数相比的较小数是多少,和自己相比时为0,于是有个主对角线为0的矩阵,求原数列

    饶文津
  • 【GPLT】L1-002【PAT乙级】打印沙漏

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    喜欢ctrl的cxk
  • LeetCode 1292. 元素和小于等于阈值的正方形的最大边长(DP)

    请你返回元素总和小于或等于阈值的正方形区域的最大边长; 如果没有这样的正方形区域,则返回 0 。

    Michael阿明
  • Java Varargs 可变参数使用

    "Varargs"是 “variable number of arguments”的意思。有时候也被简单的称为 “variable arguments”。

    HoneyMoose

扫码关注云+社区

领取腾讯云代金券