洛谷P1005 矩陣取數遊戲

這道題一拿到就覺得要用高精度做，可是我這輩子真不想寫高精度了，看來題解後才發現有一種__int128的類型在網上的OJ上通用，這種類型支援2^128這麼大，讓我可歡喜了，但是我在網上查了些資料，發現在CodeBlocks上無法使用，但是DevC++上可以，有時候比賽支援，但不成定數。

__int128的介紹也就這麼多了，比賽的時候酌情使用，但不可否認的是，他給我們解這道題提供了極大的友善

首先我們來看看這道題的做法，在不用高精度的情況下，這道題還是需要點思維的，首先從題意可知我們可以對每一排獨立分析

f[i][j]表示這一排還剩下從第i位到第j位
f[i][j]=max(f[i+1][j]+base[m-(j-i)]*a[i],f[i][j-1]+base[m-(j-i)]*a[j]);//轉移方程
           

剩下的就簡單了，那麼(此代碼用記憶話搜尋實作)

上代碼：

#include <bits/stdc++.h>
#define lll __int128
using namespace std;
int n,m,a[81];
lll f[81][81],ans=0,base[81];
void getbase(){
    base[0]=1;
    for(int i=1;i<=m;i++){
        base[i]=base[i-1]*2;
    }
}
void print(lll x){
    if(!x)
        return;
    else
        print(x/10);
    putchar(x%10+'0');
}
lll dp(int l,int r){
    if(f[l][r]>=0)
        return f[l][r];
    int k=m-(r-l);
    if(r-l>=1)
        f[l][r]=max(dp(l+1,r)+base[k]*a[l],dp(l,r-1)+base[k]*a[r]);
    else
        f[l][r]=a[l]*base[k];
    return f[l][r];
}
int main()
{
    scanf("%d %d",&n,&m);
    getbase();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            scanf("%d",&a[j]);
        }
        memset(f,-1,sizeof(f));
        ans+=dp(1,m);
    }
    if(!ans)
        printf("0");
    else
        print(ans);
    return 0;
}