链接：https://ac.nowcoder.com/acm/contest/886/J
来源：牛客网
时间限制：C/C++ 2秒，其他语言4秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
Rowlet is playing a very popular game in the pokemon world. Recently, he has encountered a problem and wants to ask for your help.
In this game, there is a technology tree system. There are n kinds of technology in this game, each of them has m levels numbered from 1 to m. In the beginning, all technologies have no level (regard as level 0). When the i-th technology is at the (j - 1)-th level, the player can pay cijc_{i j}cij pokedollars (currency used in this game) to upgrade this technology into the j-th level. However, sometimes upgrading is so easy that the cost might be negative, which implies the player may gain profit from upgrading technologies.
Moreover, if all technologies have been upgraded to level j, the player will gain an additional profit of djd_{j}dj pokedollars. However, sometimes too many technologies of the same level might be confusing, hence the profit can be negative as well.
Rowlet wants to determine the optimal strategy that can bring him the most pokedollars. Help him to find the maximum gain. Note that Rowlet may upgrade nothing, and in that case, the profit is zero.
输入描述:
There are multiple test cases. The first line contains an integer T (1≤T≤101 \leq T \leq 101≤T≤10), indicating the number of test cases. Test cases are given in the following.
For each test case, the first line contains two integers n, m (1≤n,m≤10001 \leq n, m \leq 10001≤n,m≤1000), representing the number of technologies and the number of levels respectively.
The i-th of the next n lines contains m integers, where the j-th number is cijc_{i j}cij (−109≤cij≤109-10^{9} \leq c_{i j} \leq 10^{9}−109≤cij≤109).
The last line contains m integers, where the j-th number is djd_{j}dj (−109≤dj≤109-10^{9} \leq d_{j} \leq 10^{9}−109≤dj≤109).
We ensure that the sum of n⋅mn \cdot mn⋅m in all test cases is at most 2×1062 \times 10^{6}2×106. 输出描述:
For each test case, output "Case #x: y" in one line (without quotes), where x indicates the case number starting from 1, and y denotes the answer(in pokedollars) to this test case. 示例1
输入
2
2 2
1 2
2 -1
4 1
3 3
1 2 3
1 2 3
1 2 3
6 7 8
输出
Case #1: 2
Case #2: 4 题目大意:有一棵科技树,第i个科技升级到j水平需要 花费 Cij,如果所有科技都升级到 j水平会奖励一部分(如果奖励为负.那就扣钱).问可以得到最大多少的利益.
题目思路:根据这个题的思路,我们可以在过程中想出好多种情况,比如只升级一个 或者两个科技升到满级,或者再附带其他科技.其实我们考虑这个题的最终状态,一共有m+1种,第一种就是 连第一个等级都没有同时达到,共同达到 1,2,3.......m种等级,那么根据此时的贪心思路,我们枚举状态下需要保证最优,需要知道 当前状态下,后面没达到的最优状态,那就是至多有n-1条链,如果多余n-1条,就会满到下一个等级.而这n-1条链长短不一,而且也不一定都选怎么处理呢,我们知道最小子段和可以处理以i结束的不知道从什么地方开始的最小和,所以此时我们可以倒过来想,从n到i的最小子段和,也就是现在的 最小子段和就是 从i开始 连续并且不知道连续到哪的一个最小和(为什么求最小,因为我们这是花费的钱),但是算完之后我们还需要直到那些链选哪些链不选,那么我们只需要判断一下,最小子串和还大于0,那么说明不选,直接将其变为0,然后我们最后处理的时候减去最大值选n-1条即可.所以答案就是枚举完所有状态的最优值.
第i层满状态的方程都是 ans=sumd[i](获得贡献)-sumc[i](前面n*i的矩阵和,因为是花费所以减)-maxl(贪心得到最优值,因为花费所以还是负的)
具体细节看代码叭
所以AC代码:
#include <bits/stdc++.h>
#define E 2.718
using namespace std;
typedef long long ll;
const ll INF=1e15+5;
const int maxn=2e6+8;
const double eps=1e-10;
const ll mod=998244353;
ll n,m;
ll dp[1005][1005];//最小子串和
ll d[1005];
ll mp[1005][1005];
ll r[1005];//每一列的和
ll ls[1005];//d的和
int main()
{
int cas=0;
int T;scanf("%d",&T);
while(T--)
{
ls[0]=0;
scanf("%lld%lld",&n,&m);
for(int i=0;i<=m;i++) r[i]=0;
for(int i=1;i<=n;i++)
{
for(int k=1;k<=m;k++)
{
scanf("%lld",&mp[i][k]);
r[k]+=mp[i][k];
}
}
for(int i=1;i<=m;i++)
r[i]=r[i-1]+r[i];
for(int i=1;i<=m;i++) scanf("%lld",&d[i]);
for(int i=1;i<=n;i++)
{
dp[i][m+1]=0;
for(int k=m;k>=1;k--)
dp[i][k]=min(dp[i][k+1]+mp[i][k],mp[i][k]);//从后往前跑最小子串和
}
for(int i=1;i<=n;i++)
for(int k=1;k<=m;k++) if(dp[i][k]>0) dp[i][k]=0;
for(int i=1;i<=m;i++) ls[i]=ls[i-1]+d[i];
ll res=0;
for(int i=1;i<=m;i++)我枚举当前已经满了i-1层状态
{
ll x=0,maxl=-INF;
for(int k=1;k<=n;k++)
{
maxl=max(dp[k][i],maxl);
x+=dp[k][i];
}
res=max(ls[i-1]-(x-maxl)-r[i-1],res);
}
res=max(res,ls[m]-r[m]);//最后加个特判
printf("Case #%d: %lld\n",++cas,res);
}
return 0;
}
京公网安备 11010502036488号