NOIP2007提高组第二轮T3：矩阵取数游戏

$n \times m$ 的矩阵，矩阵中的每个元素

a_{i,j}

$a_{i, j}$ 均为非负整数。游戏规则如下：

每次取数时须从每行各取走一个元素，共
每次取走的各个元素只能是该元素所在行的行首或行尾；
每次取数都有一个得分值，为每行取数的得分之和，每行取数的得分 = 被取走的元素值 $2^i ×2i，其中 i i i 表示第 i i i 次取数（从 1 1 1 开始编号）；$
游戏结束总得分为

帅帅想请你帮忙写一个程序，对于任意矩阵，可以求出取数后的最大得分。

输入 格式

输入文件包括

n+1

$n + 1$ 行：

第一行为两个用空格隔开的整数

$n$ 和

$m$ 。

第

∼

2sim n+1

$2 \sim n + 1$ 行为

n time s m

$n \times m$ 矩阵，其中每行有

$m$ 个用单个空格隔开的非负整数。

输出 格式

输出文件仅包含

$1$ 行，为一个整数，即输入矩阵取数后的最大得分。

样例 #1

样例输入 #1

2 3
1 2 3
3 4 2

样例输出 #1

提示

【数据范围】

对于

60%

$60%$ 的数据，满足

≤

1le n,mle 30

$1 \leq n, m \leq 30$ ，答案不超过

10^{16}

$1 0^{16}$ 。
对于

100

100%

$100%$ 的数据，满足

≤

1le n,mle 80

$1 \leq n, m \leq 80$ ，

≤

1000

0le a_{i,j}le1000

$0 \leq a_{i, j} \leq 1000$ 。

算法思想

根据题目描述，每次都要从各行的行首或行尾取走一个元素，一共取

$m$ 次，求出取数后的最大得分。不难发现，在取数的过程中，行与行之间相互独立，因此可以对每一行单独计算取数的最大得分。

根据得分的计算规则，每行取数的得分 = 被取走的元素值

times 2^i

$\times 2^{i}$ ，其中

$i$ 表示第

$i$ 次取数（从

$1$ 开始编号），而每次取数有两种情况，行首或行尾取走一个元素，如下图所示：

在这里插入图片描述
那么，每行取数的得分之和的最大值除了与被取走的元素值

times 2^i

$\times 2^{i}$ 有关，还与剩余区间的得分相关，可以使用区间型动态规划来处理。

状态表示

[

]

[

]

f[i][j]

$f [i] [j]$ 表示在一行中区间

[

]

[i,j]

$[i, j]$ 取数的最大得分。

状态 计算

根据取数规则，只能取走行首或行尾元素，因此要计算当前状态

[

]

[

]

f[i][j]

$f [i] [j]$ ，可以根据取数的位置分成两种情况：

取走行首元素，也就是 $w[i]times2^{m-j+i} f[i+1][j]+w[i]×2m−j+i$
取走行尾元素，也就是 $w[j]times2^{m-j+i} f[i][j−1]+w[j]×2m−j+i$

其中：

w $次取数，因此应加上wtimes2^{m-j+i}$$

初始状态

注意，当区间长度为

$1$ 时，

[

]

[

]

f[i+1][j]

$f [i + 1] [j]$ 、

[

]

[

]

f[i+1][j]

$f [i + 1] [j]$ 表示的区间为空，此时状态应为

$0$ 。

时间 复杂度

状态数为

mtimes m

$m \times m$ ，状态计算的时间复杂度为

(

)

O(1)

$O (1)$ ，一共要计算

$n$ 行，因此时间复杂度为

(

)

512000

O(ntimes m^2)=80^3=512000

$O (n \times m^{2}) = 8 0^{3} = 512000$ 。

代码 实现（60分）

对于

60%

$60%$ 的数据，满足

≤

1le n,mle 30

$1 \leq n, m \leq 30$ ，答案不超过

10^{16}

$1 0^{16}$ 。

#include &lt;iostream&gt;
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 &lt;= m; len ++)
        //枚举开始位置
        for(int i = 1; i + len - 1 &lt;= 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 &gt;&gt; n &gt;&gt; m;
    LL res = 0;
    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <= m; j ++)
           	cin &gt;> w[j];
        res += work();
    }
    cout << res << endl;
    return 0;
}

代码 实现（100分）

对于

100

100%

$100%$ 的数据，满足

≤

1le n,mle 80

$1 \leq n, m \leq 80$ ，

≤

1000

0le a_{i,j}le1000

$0 \leq a_{i, j} \leq 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实现

由于

≤

mle 80

$m \leq 80$ ，

≤

1000

0le a_{i,j}le1000

$0 \leq a_{i, j} \leq 1000$ ，那么每行的最大值为

1000

80times1000times2^{80}

$80 \times 1000 \times 2^{80}$ ，不会超过

100

2^{100}

$2^{100}$ ，因此可以使用__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不能直接输出__int128
    print(res);
    return 0;
}

原文地址:https://blog.csdn.net/qiaoxinwei/article/d etails/134595365

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。

如若转载，请注明出处：http://www.7code.cn/show_17133.html

如若内容造成侵权/违法违规/事实不符，请联系代码007邮箱：suwngjj01@126.com进行投诉反馈，一经查实，立即删除！

声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。

元素取数矩阵

题目 链接

题目 描述

输入 格式

输出 格式

样例 #1

样例输入 #1

样例输出 #1

提示

算法思想

状态表示

状态 计算

初始状态

时间 复杂度

代码 实现（60分）

代码 实现（100分）

高精度 实现

__int128实现

发表回复取消回复

样例 #1

样例输入 #1

样例输出 #1

算法思想

状态表示

初始状态

代码实现（60分）

代码实现（100分）

__int128实现

相关文章

发表回复 取消回复

发表回复取消回复