【洛谷】【区间dp】【高精度】P1005 [NOIP2007 提高组] 矩阵取数游戏

题目描述
  帅帅经常跟同学玩一个矩阵取数游戏：对于一个给定的 n×m 的矩阵，矩阵中的每个元素 ai,j 均为非负整数。游戏规则如下：

每次取数时须从每行各取走一个元素，共 n个。经过 m次后取完矩阵内所有元素；
每次取走的各个元素只能是该元素所在行的行首或行尾；
每次取数都有一个得分值，为每行取数的得分之和，每行取数的得分 = 被取走的元素值 x2i，其中 i表示第 i次取数（从 1开始编号）；
游戏结束总得分为 m次取数得分之和。
  帅帅想请你帮忙写一个程序，对于任意矩阵，可以求出取数后的最大得分。

输入格式
  输入文件包括 n+1 行：

  第一行为两个用空格隔开的整数 n和 m。

  第 2~ n+1 行为n×m矩阵，其中每行有 m 个用单个空格隔开的非负整数。

输出格式
  输出文件仅包含 1行，为一个整数，即输入矩阵取数后的最大得分。

测试样例

输入
2 3
1 2 3
3 4 2

输出
82

解题思路
1.状态转移方程

  设fl[i]为左端点为l，右端点为l+len,第i行取数所能获得的最大值，则状态转移方程如下
f [ l ] [ l + l e n ] [ i ] = m a x ( 2 ∗ f [ l + 1 ] [ l + l e n ] [ i ] + 2 ∗ a [ i ] [ l ] , 2 ∗ f [ l ] [ l + l e n − 1 ] [ i ] + 2 ∗ a [ i ] [ l + l e n ] ) fl[i]=max(2fl+1[i]+2ai,2fl[i]+2ai)
fl[i]=max(2∗fl+1[i]+2∗ai,2∗fl[i]+2∗ai)

  可以化简为
f [ l ] [ l + l e n ] [ i ] = m a x ( f [ l + 1 ] [ l + l e n ] [ i ] + a [ i ] [ l ] , f [ l ] [ l + l e n − 1 ] [ i ] + a [ i ] [ l + l e n ] ) ∗ 2 fl[i]=max(fl+1[i]+ai,fl[i]+ai)*2
fl[i]=max(fl+1[i]+ai,fl[i]+ai)∗2

2.高精度的问题

  这个题目虽然每个数不是很大，但是最后的结果会超出64位，所以需要用到高精度，文末提供了两种高精度的方法，第一种是用__int128，第二种是自己写一个高精度模板。

3.一定要判断全0的情况，否则会有一个测试样例过不去。

AC代码(__int128)

#include<iostream>
#include<bits/stdc++.h>
using namespace std;

#define ll __int128
#define MAX 85
//__int128的输出
void print(ll x)
{
    if(x>9) print(x/10);
    putchar(x%10 + '0');
}
//__int128的输入
void input(ll &s)
{
    s = 0;
    char c = ' ';
    while(c<'0' || c>'9') c = getchar();
    while(c>='0' && c<='9')
    {
        s = s*10+c-'0';
        c = getchar();
    }
}

int main()
{
    int n,m;
    ll sum = 0;
    cin>>n>>m;
    ll a[MAX][MAX];
    ll fun[MAX][MAX][MAX] = {0};
    //读入数据
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            input(a[i][j]);
        }
    }
    //开始进行计算，区间dp
    for(int i=1;i<=n;i++)
    {
        for(int len=0;len<m;len++)
        {
            for(int l=1;l<=m;l++)
            {
                fun[l][l+len][i] = max((fun[l+1][l+len][i]+a[i][l]),(fun[l][l+len-1][i]+a[i][l+len])) * 2;
            }
        }
    }
    //计算最后结果，高精度
    for(int i=1;i<=n;i++)
    {
        sum += fun[1][m][i];
    }
    print(sum);
    return 0;
}

AC代码(自定义高精度模板)

#include<iostream>
#include<bits/stdc++.h>
using namespace std;

#define MAX 85
long long p = 1e18;
//定义128位整数
struct int128
{
    long long high;
    long long low;
};
//取最大值
int128 max(int128 a,int128 b)
{
    if(a.high > b.high) return a;
    else if(a.high < b.high) return b;
    else if(a.low > b.low) return a;
    else if(a.low < b.low) return b;
    else return a;
}
//128位+128位
int128 operator + (int128 a,int128 b)
{
    int128 k;
    k.high = 0;
    k.low = 0;
    k.low = a.low + b.low;
    k.high = k.low / p + a.high + b.high;
    k.low = k.low % p;
    return k;
}
//128位*64位
int128 operator * (int128 a,int b)
{
    int128 k;
    k.high = 0;
    k.low = 0;
    k.low = a.low * b;
    k.high = k.high + k.low / p + a.high * b;
    k.low = k.low % p;
    return k;
}

int main()
{
    int n,m;
    int128 num[MAX][MAX],fun[MAX][MAX][MAX],sum;
    scanf("%d%d",&n,&m);
    fun[MAX][MAX][MAX];
    //读入数据
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            scanf("%lld",&num[i][j].low);
        }
    }
    //区间dp
    for(int i=1;i<=n;i++)
    {
        for(int len=0;len<m;len++)
        {
            for(int l=1;l<=m;l++)
            {
                fun[l][l+len][i] = max(fun[l+1][l+len][i]+num[i][l],fun[l][l+len-1][i]+num[i][l+len]) * 2;
            }
        }
    }

    for(int i=1;i<=n;i++)
    {
        sum = sum + fun[1][m][i];
    }
    //注意低位如果位数不够要补零
    if(sum.high == 0) printf("%lld",sum.low);
    else printf("%lld%018lld",sum.high,sum.low);
    return 0;
}