电子商务网站建设知识,秒收录网站,有哪些公司的网站做的很好看,海报设计在线生成来源#xff1a;牛客网#xff1a; 文章目录题目描述题解#xff1a;代码#xff1a;时间限制#xff1a;C/C 1秒#xff0c;其他语言2秒
空间限制#xff1a;C/C 262144K#xff0c;其他语言524288K
64bit IO Format: %lld题目描述 帅帅经常跟同学玩一个矩阵取数游戏牛客网
文章目录题目描述题解代码时间限制C/C 1秒其他语言2秒
空间限制C/C 262144K其他语言524288K
64bit IO Format: %lld题目描述 帅帅经常跟同学玩一个矩阵取数游戏对于一个给定的n*m的矩阵矩阵中的每个元素aij均为非负整数。游戏规则如下 1.每次取数时须从每行各取走一个元素共n个。m次后取完矩阵所有元素 2.每次取走的各个元素只能是该元素所在行的行首或行尾 3.每次取数都有一个得分值为每行取数的得分之和每行取数的得分 被取走的元素值 * 2i其中i表示第i次取数从1开始编号 4.游戏结束总得分为m次取数得分之和。 帅帅想请你帮忙写一个程序对于任意矩阵可以求出取数后的最大得分。 输入描述: 第1行为两个用空格隔开的整数n和m。 第2~n1行为n*m矩阵其中每行有m个用单个空格隔开的非负整数。 输出描述: 输出一个整数即输入矩阵取数后的最大得分。 示例1 输入 复制
2 3
1 2 3
3 4 2输出 复制
82说明 第1次第1行取行首元素第2行取行尾元素本次得分为1 * 21 2 * 21 6 第2次两行均取行首元素本次得分为2 * 22 3 * 22 20 第3次得分为3 * 23 4 * 23 56。 总得分为6 20 56 82 示例2 输入 复制
1 4
4 5 0 5输出 复制
122示例3 输入 复制
2 10
96 56 54 46 86 12 23 88 80 43
16 95 18 29 30 53 88 83 64 67输出 复制
316994备注: 60%的数据满足1 ≤ n, m ≤ 30, 答案不超过1016 100%的数据满足1 ≤ n, m ≤ 80, 0 ≤ aij ≤ 1000
题解
每一行都进行的相同操作且每一行的操作都互不影响所以我们可以一行一行的考虑算出每一行的最佳情况然后求和 这样就降低难度维度 先看第一行只能在行首行尾取如果我们要知道区间[1,m]的最佳情况就要知道[1,m-1]和[2,n]的最优解因为是由他俩推过去的依次类推 dp[i][j]表示i到j区间的最优解 dp[i][j]min(dp[i1][j]2k *a[i] dp[i][j-1] 2k *a[j]) 由内向外扩展的过程 区间长度为n时k取1长度每缩短一次k相当于第k次取
因为我们乘以2是依次增多的所以每次都乘以2 本题是需要高精度的当然也可以使用__int128 快读快输 黑魔法
代码
#includebits/stdc.h
using namespace std;
#define _t __int128
inline _t read()
{_t x0,f1;char chgetchar();while(ch0||ch9){if(ch-)f1;chgetchar();}while(ch0ch9){xx*10ch-0;chgetchar();}return x*f;
}
inline void put(_t x)
{if(x0){putchar(-);x-x;}if(x9)put(x/10);putchar(x%100);
}
_t n,m,res;
_t a[103][103],dp[103][104];
_t cul(_t b[])
{for(_t len1;lenm;len){for(_t l1,rllen-1;rm;l,rllen-1){dp[l][r]max(dp[l1][r]b[l],dp[l][r-1]b[r]);dp[l][r]2*dp[l][r];}} return dp[1][m];
}
int main()
{nread(),mread();for(int i1;in;i)for(int j1;jm;j)a[i][j]read();for(int i1;in;i){memset(dp,0,sizeof(dp));rescul(a[i]);}put(res);return 0;
}
