焦作网站建设设计,做直播网站前端,网站建设合同百度文库,如何做好宣传推广题目描述
帅帅经常跟同学玩一个矩阵取数游戏#xff1a;对于一个给定的 n \times mnm 的矩阵#xff0c;矩阵中的每个元素 a_{i,j}ai,j 均为非负整数。游戏规则如下#xff1a;
每次取数时须从每行各取走一个元素#xff0c;共 nn 个。经过 mm 次后取完矩阵内所有元素对于一个给定的 n \times mn×m 的矩阵矩阵中的每个元素 a_{i,j}ai,j 均为非负整数。游戏规则如下
每次取数时须从每行各取走一个元素共 nn 个。经过 mm 次后取完矩阵内所有元素每次取走的各个元素只能是该元素所在行的行首或行尾每次取数都有一个得分值为每行取数的得分之和每行取数的得分 被取走的元素值 \times 2^i×2i其中 ii 表示第 ii 次取数从 11 开始编号游戏结束总得分为 mm 次取数得分之和。
帅帅想请你帮忙写一个程序对于任意矩阵可以求出取数后的最大得分。
输入格式
输入文件包括 n1n1 行
第一行为两个用空格隔开的整数 nn 和 mm。
第 2\sim n12∼n1 行为 n \times mn×m 矩阵其中每行有 mm 个用单个空格隔开的非负整数。
输出格式
输出文件仅包含 11 行为一个整数即输入矩阵取数后的最大得分。
输入数据 1
2 3
1 2 3
3 4 2Copy
输出数据 1
82Copy
数据范围与约定
对于 60\%60% 的数据满足 1\le n,m\le 301≤n,m≤30答案不超过 10^{16}1016。 对于 100\%100% 的数据满足 1\le n,m\le 801≤n,m≤800\le a_{i,j}\le10000≤ai,j≤1000。
NOIP 2007 提高组 第三题
变更记录
因本题原题与P0769 字符串的展开重复
本题更换为# [NOIP2007提高组] 矩阵取数游戏 代码:
#include cstdio
#include cstring
#include iostream
using namespace std;
struct dzs{int ws,li[20];
};
int a[81][81],n,m;
dzs f[2][81][81][81],er[81],an,ans,pss1,pss2;
dzs gjc(int p1,dzs p2){ //高精乘单精for(int i1;ip2.ws;i)p2.li[i]*p1;for(int i1;ip2.ws5;i){if(ip2.wsp2.li[i]!0)p2.wsi;if(p2.li[i]9999)p2.li[i1]p2.li[i]/10000,p2.li[i]%10000;}return p2;
}
dzs gjj(dzs p1,dzs p2){ //高精加dzs p3;memset(p3.li,0,sizeof(p3.li));p3.ws1;for(int i1;imax(p1.ws,p2.ws);i)p3.li[i]p2.li[i]p1.li[i];for(int i1;ip2.ws5;i){if(ip3.wsp3.li[i]!0)p3.wsi;if(p3.li[i]9999)p3.li[i1]p3.li[i]/10000,p3.li[i]%10000;}return p3;
}
dzs maxd(dzs p1,dzs p2){ //取大数if(p1.wsp2.ws)return p1;if(p2.wsp1.ws)return p2;for(int ip1.ws;i1;i--){if(p1.li[i]p2.li[i])return p1;if(p1.li[i]p2.li[i])return p2;}return p1;
}
int print(dzs p1){for(int ip1.ws;i1;i--){if(ip1.ws){coutp1.li[i];continue;}if(p1.li[i]10)cout000;else if(p1.li[i]100)cout00;else if(p1.li[i]1000)cout0;coutp1.li[i];}
}
int main(){cinnm;for(int i1;in;i)for(int j1;jm;j)cina[i][j];er[1].li[1]2;er[1].ws1;for(int i2;im;i){er[i]gjc(2,er[i-1]);}//计算2^i(gao jing)for(int k1;kn;k)//第k行for(int i1;im;i){//第i次取数for(int j1;ji;j){f[0][k][i][j]gjj(maxd(f[0][k][i-1][j-1],f[1][k][i-1][m-(i-j)1]),gjc(a[k][j],er[i]));}for(int jm-i1;jm;j){f[1][k][i][j]gjj(maxd(f[1][k][i-1][j1],f[0][k][i-1][i-(m-j1)]),gjc(a[k][j],er[i]));}}memset(ans.li,0,sizeof(ans.li));ans.ws1;for(int k1;kn;k){an.ws1;memset(an.li,0,sizeof(an.li));for(int i1;im;i){anmaxd(an,f[0][k][m][i]);anmaxd(an,f[1][k][m][i]);}ansgjj(ans,an);}print(ans);coutendl;return 0;
}
