题目链接
题目描述
n
×
,
j
- 每次取数时须从每行各取走一个元素，共
n
n
n 个。经过
m 次后取完矩阵内所有元素； - 每次取走的各个元素只能是该元素所在行的行首或行尾；
- 每次取数都有一个得分值，为每行取数的得分之和，每行取数的得分 = 被取走的元素值
×
2
×2i，其中
i 表示第i
i
i 次取数（从1
1
1 开始编号）； - 游戏结束总得分为
m
m
m 次取数得分之和。
帅帅想请你帮忙写一个程序，对于任意矩阵，可以求出取数后的最大得分。
输入格式
n
+
1
n+1
n+1 行：
n
n
n 和
m
m
m。
第
2
∼
n
+
1
2sim n+1
2∼n+1 行为
n
×
m
n×m 矩阵，其中每行有
m
m
m 个用单个空格隔开的非负整数。
输出格式
1
1
样例 #1
样例输入 #1
2 3
1 2 3
3 4 2
样例输出 #1
82
提示
对于
60
%
60%
60% 的数据，满足
1
≤
n
,
m
≤
30
1≤n,m≤30，答案不超过
1
0
16
10^{16}
1016。
对于
100
%
100%
100% 的数据，满足
1
≤
n
,
m
≤
80
1≤n,m≤80，
0
≤
i
,
j
≤
1000
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]
[
i
,
j
]
[i,j]
[i,j]取数的最大得分。
状态计算
f
[
i
]
[
j
]
f[i][j]
- 取走行首元素，也就是
i
i
i位置上的元素，得分为f
[
i
+
1
]
[
j
]
+
w
[
i
]
×
2
m
−
j
+
i
f[i+1][j] + w[i]times2^{m-j+i}
f[i+1][j]+w[i]×2m−j+i - 取走行尾元素，也就是
j
j
j位置上的元素，得分为f
[
i
]
[
j
−
1
]
+
w
[
j
]
×
2
m
−
j
+
i
f[i][j-1] + w[j]times2^{m-j+i}
f[i][j−1]+w[j]×2m−j+i
其中：
-
f
[
i
+
1
]
[
j
]
f[i+1][j]
f[i+1][j]、f
[
i
+
1
]
[
j
]
f[i+1][j]
f[i+1][j]表示剩余区间的得分最大值； - w
表示取数位置上元素的分值。对区间
表示取数位置上元素的分值。对区间
表示取数位置上元素的分值。对区间[i,j]取数时，意味着之前已经取走了
取数时，意味着之前已经取走了
取数时，意味着之前已经取走了m-(j-i+1)
个数，当前是第m-j+i次取数，因此应加上
次取数，因此应加上
次取数，因此应加上wtimes2^{m-j+i}$
初始状态
注意，当区间长度为
1
1
1时，
f
[
i
+
1
]
[
j
]
f[i+1][j]
f[i+1][j]、
f
[
i
+
1
]
[
j
]
f[i+1][j]
0
0
0。
时间复杂度
状态数为
m
×
m
O
(
1
)
O(1)
O(1)，一共要计算
n
n
O
(
n
×
m
2
)
=
8
0
3
=
512000
O(n×m2)=803=512000。
代码实现（60分）
对于
60
%
60%
60% 的数据，满足
1
≤
n
,
m
≤
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
1le n,mle 80
1≤n,m≤80，
0
≤
i
,
j
≤
1000
0le a_{i,j}le1000
0≤ai,j≤1000。
高精度实现
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
typedef vector<int> 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位则补0
for (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初始化为0
VI 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
mle 80
m≤80，
0
≤
a
i
,
j
≤
1000
0le a_{i,j}le1000
0≤ai,j≤1000，那么每行的最大值为
80
×
1000
×
2
80
80×1000×280，不会超过
2
100
2^{100}
2100，因此可以使用__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不能直接输出__int128
print(res);
return 0;
}
原文地址:https://blog.csdn.net/qiaoxinwei/article/details/134595365
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若转载，请注明出处：http://www.7code.cn/show_17133.html
如若内容造成侵权/违法违规/事实不符，请联系代码007邮箱：suwngjj01@126.com进行投诉反馈，一经查实，立即删除！
