郑州市的实惠推广网站,ps怎样做网站大图,泰安焦点网络有限公司,国基建设集团有限公司网站题目链接
[NOIP2007 提高组] 矩阵取数游戏
题目描述
帅帅经常跟同学玩一个矩阵取数游戏#xff1a;对于一个给定的 n m n \times m nm 的矩阵#xff0c;矩阵中的每个元素 a i , j a_{i,j} ai,j 均为非负整数。游戏规则如下#xff1a;
每次取数时须从每行各取走一…题目链接
[NOIP2007 提高组] 矩阵取数游戏
题目描述
帅帅经常跟同学玩一个矩阵取数游戏对于一个给定的 n × m n \times m n×m 的矩阵矩阵中的每个元素 a i , j a_{i,j} ai,j 均为非负整数。游戏规则如下
每次取数时须从每行各取走一个元素共 n n n 个。经过 m m m 次后取完矩阵内所有元素每次取走的各个元素只能是该元素所在行的行首或行尾每次取数都有一个得分值为每行取数的得分之和每行取数的得分 被取走的元素值 × 2 i \times 2^i ×2i其中 i i i 表示第 i i i 次取数从 1 1 1 开始编号游戏结束总得分为 m m m 次取数得分之和。
帅帅想请你帮忙写一个程序对于任意矩阵可以求出取数后的最大得分。
输入格式
输入文件包括 n 1 n1 n1 行
第一行为两个用空格隔开的整数 n n n 和 m m m。
第 2 ∼ n 1 2\sim n1 2∼n1 行为 n × m n \times m n×m 矩阵其中每行有 m m m 个用单个空格隔开的非负整数。
输出格式
输出文件仅包含 1 1 1 行为一个整数即输入矩阵取数后的最大得分。
样例 #1
样例输入 #1
2 3
1 2 3
3 4 2样例输出 #1
82提示
【数据范围】
对于 60 % 60\% 60% 的数据满足 1 ≤ n , m ≤ 30 1\le n,m\le 30 1≤n,m≤30答案不超过 1 0 16 10^{16} 1016。 对于 100 % 100\% 100% 的数据满足 1 ≤ n , m ≤ 80 1\le n,m\le 80 1≤n,m≤80 0 ≤ a i , j ≤ 1000 0\le a_{i,j}\le1000 0≤ai,j≤1000。
算法思想
根据题目描述每次都要从各行的行首或行尾取走一个元素一共取 m m m次求出取数后的最大得分。不难发现在取数的过程中行与行之间相互独立因此可以对每一行单独计算取数的最大得分。
根据得分的计算规则每行取数的得分 被取走的元素值 × 2 i \times 2^i ×2i其中 i i i 表示第 i i i 次取数从 1 1 1 开始编号而每次取数有两种情况行首或行尾取走一个元素如下图所示 那么每行取数的得分之和的最大值除了与被取走的元素值 × 2 i \times 2^i ×2i有关还与剩余区间的得分相关可以使用区间型动态规划来处理。
状态表示 f [ i ] [ j ] f[i][j] f[i][j]表示在一行中区间 [ i , j ] [i,j] [i,j]取数的最大得分。
状态计算
根据取数规则只能取走行首或行尾元素因此要计算当前状态 f [ i ] [ j ] f[i][j] f[i][j]可以根据取数的位置分成两种情况
取走行首元素也就是 i i i位置上的元素得分为 f [ i 1 ] [ j ] w [ i ] × 2 m − j i f[i1][j] w[i]\times2^{m-ji} f[i1][j]w[i]×2m−ji取走行尾元素也就是 j j j位置上的元素得分为 f [ i ] [ j − 1 ] w [ j ] × 2 m − j i f[i][j-1] w[j]\times2^{m-ji} f[i][j−1]w[j]×2m−ji
其中 f [ i 1 ] [ j ] f[i1][j] f[i1][j]、 f [ i 1 ] [ j ] f[i1][j] f[i1][j]表示剩余区间的得分最大值w 表示取数位置上元素的分值。对区间 表示取数位置上元素的分值。对区间 表示取数位置上元素的分值。对区间[i,j] 取数时意味着之前已经取走了 取数时意味着之前已经取走了 取数时意味着之前已经取走了m-(j-i1) 个数当前是第 个数当前是第 个数当前是第m-ji 次取数因此应加上 次取数因此应加上 次取数因此应加上w\times2^{m-ji}$
初始状态
注意当区间长度为 1 1 1时 f [ i 1 ] [ j ] f[i1][j] f[i1][j]、 f [ i 1 ] [ j ] f[i1][j] f[i1][j]表示的区间为空此时状态应为 0 0 0。
时间复杂度
状态数为 m × m m\times m m×m状态计算的时间复杂度为 O ( 1 ) O(1) O(1)一共要计算 n n n行因此时间复杂度为 O ( n × m 2 ) 8 0 3 512000 O(n\times m^2)80^3512000 O(n×m2)803512000。
代码实现60分
对于 60 % 60\% 60% 的数据满足 1 ≤ n , m ≤ 30 1\le n,m\le 30 1≤n,m≤30答案不超过 1 0 16 10^{16} 1016。
#include iostream
using namespace std;
typedef long long LL;
const int N 100;
int n, m;
LL w[N], f[N][N];
LL work()
{//枚举区间长度for(int len 1; len m; len )//枚举开始位置for(int i 1; i len - 1 m; i ){int j i len - 1; //结束位置int t m - j i; //第t次取数f[i][j] max(f[i 1][j] w[i] * (1 t), f[i][j - 1] w[j] * (1 t));}return f[1][m];
}
int main()
{cin n m;LL res 0;for(int i 1; i n; i ){for(int j 1; j m; j )cin w[j];res work();}cout res endl;return 0;
}代码实现100分
对于 100 % 100\% 100% 的数据满足 1 ≤ n , m ≤ 80 1\le n,m\le 80 1≤n,m≤80 0 ≤ a i , j ≤ 1000 0\le a_{i,j}\le1000 0≤ai,j≤1000。
高精度实现
#include iostream
#include cstring
#include vector
using namespace std;
typedef vectorint VI;
typedef long long LL;
const int N 90, D 1e8; //表示大整数每个部分的位数
int n, m;
int w[N];
VI f[N][N];
VI power2[N];VI add(VI a, VI b)
{static VI c;c.clear();for (int i 0, t 0; i a.size() || i b.size() || t; i ){if (i a.size()) t a[i];if (i b.size()) t b[i];c.push_back(t % D); //压位t / D; //压位}return c;
}VI mul(VI a, int b)
{static VI c;c.clear();LL t 0;for (int i 0; i a.size() || t; i ){if (i a.size()) t (LL)a[i] * b;c.push_back(t % D);t / D;}return c;
}VI Max(VI A, VI B)
{if (A.size() ! B.size()){if (A.size() B.size()) return A;return B;}for (int i A.size() - 1; i 0; i -- ){if (A[i] B[i]) return A;if (A[i] B[i]) return B;}return A;
}void print(VI a)
{printf(%d, a.back());//压位处理中间位数不足8位则补0for (int i a.size() - 2; i 0; i -- ) printf(%08d, a[i]); puts();
}VI work()
{for (int len 1; len m; len )for (int i 1; i len - 1 m; i ){int j i len - 1;int t m - j i;//区间长度为1时if (i j) f[i][j] mul(power2[t], w[j]);else{auto left add(mul(power2[t], w[i]), f[i 1][j]);auto right add(mul(power2[t], w[j]), f[i][j - 1]);f[i][j] Max(left, right);}}return f[1][m];
}int main()
{cin n m;//求2的次方power2[0] {1};for (int i 1; i m; i ) power2[i] mul(power2[i - 1], 2);//将res初始化为0VI res(1, 0);for (int i 1; i n; i ){for (int j 1; j m; j ) cin w[j];res add(res, work());}print(res);return 0;
}__int128实现
由于 m ≤ 80 m\le 80 m≤80 0 ≤ a i , j ≤ 1000 0\le a_{i,j}\le1000 0≤ai,j≤1000那么每行的最大值为 80 × 1000 × 2 80 80\times1000\times2^{80} 80×1000×280不会超过 2 100 2^{100} 2100因此可以使用__int128来实现。
注意
__int128并不在c标准中它存在于GCC编译器且仅GCC4.6 及以上的64位版本支持。所以在使用时要确认OJ是否支持。cout不能直接输出__int128。
#include iostream
using namespace std;
typedef __int128 INT;
const int N 100;
int n, m;
int w[N];
INT f[N][N];
INT work()
{//枚举区间长度for(int len 1; len m; len )//枚举开始位置for(int i 1; i len - 1 m; i ){int j i len - 1; //结束位置int t m - j i; //第t次取数INT p 1; p p t;f[i][j] max(f[i 1][j] w[i] * p, f[i][j - 1] w[j] * p);}return f[1][m];
}
void print(INT x)
{if(x 9) print(x / 10);cout x % 10;
}
int main()
{cin n m;INT res 0;for(int i 1; i n; i ){for(int j 1; j m; j )cin w[j];res work();}//注意cout不能直接输出__int128print(res);return 0;
}
