帅帅经常跟同学玩一个矩阵取数游戏：对于一个给定的n×m的矩阵，矩阵中的每个元素ai,j?均为非负整数。游戏规则如下：
帅帅想请你帮忙写一个程序，对于任意矩阵，可以求出取数后的最大得分。
输入格式：
输入文件包括n+1行：
第1行为两个用空格隔开的整数n和m。
第2∽n+1行为n×m矩阵，其中每行有m个用单个空格隔开的非负整数。
输出格式：
输出文件仅包含1行，为一个整数，即输入矩阵取数后的最大得分。
NOIP 2007 提高第三题
数据范围：
60%的数据满足：1≤n,m≤30，答案不超过10^16
100%的数据满足：1≤n,m≤80，0≤ai,j?≤1000
/* 这一道题区间DP简单题 状态转移：f[i][j] = max(f[i+1][j] + map[i],f[i][j-1] + map[j])*2 此处i,j表示一段i到j的区间 *2是因为每一次dp的过程都要多乘一个2,保证答案*2^i (好像不怎么好理解233333) */ #include <bits/stdc++.h> #define ll long long using namespace std; const int maxn = 100; ll dp[maxn][maxn],ans; int n,m,x,mapp[maxn]; int main(){ scanf("%d%d",&n,&m); for(int i = 1;i <= n;i++){ memset(dp,0,sizeof(dp)); for(int i = 1;i <= m;i++){ scanf("%d",&mapp[i]); dp[i][i] = mapp[i] << 1; } for(int len = 1;len < m;len++){ for(int l = 1;l <= m;l++){ int r = l + len; dp[l][r] = max(dp[l+1][r] + mapp[l],dp[l][r-1] + mapp[r]) << 1; } } ans += dp[1][m]; } printf("%lld\n",ans); return 0; }
/* 和朴素算法的区别在于加了高精 由于答案可能达到2^80 所以要用高精 这里用的是封装的大整数类 效率可能比裸的高精慢 思路来自刘汝佳的紫书 */ #include <bits/stdc++.h> #define ll long long using namespace std; const int maxn = 100; int n,m,x,mapp[maxn]; struct BigInteger{ static const int BASE = 100000000; static const int WIDTH = 8; vector<long long> s; BigInteger(long long num = 0) {*this = num;} BigInteger operator = (long long num) { s.clear(); do{ s.push_back(num % BASE); num /= BASE; }while(num > 0); return *this; } BigInteger operator = (const string& str){ s.clear(); int x,len = (str.length() - 1) / WIDTH + 1; for(int i = 0;i < len;i++){ int end = str.length() - i*WIDTH; int start = max(0,end - WIDTH); sscanf(str.substr(start,end-start).c_str(),"%d",&x); s.push_back(x); } return *this; } BigInteger operator + (const BigInteger& b) const { BigInteger c; c.s.clear(); for(int i = 0,g = 0;;i++){ if(g == 0 && i >= s.size() && i >= b.s.size()) break; int x = g; if(i < s.size()) x += s[i]; if(i < b.s.size()) x += b.s[i]; c.s.push_back(x % BASE); g = x /BASE; } return c; } BigInteger operator * (const BigInteger& b) const { BigInteger c; c.s.resize(s.size() + b.s.size()); for(int i=0; i<s.size(); i++) for(int j = 0; j < b.s.size(); j++) c.s[i+j] += s[i] * b.s[j]; for(int i=0; i<c.s.size()-1; i++) { c.s[i+1] += c.s[i] / BASE; c.s[i] %= BASE; } while(c.s.back() == 0 && c.s.size()>1) c.s.pop_back(); return c; } BigInteger operator += (const BigInteger& b){ *this = *this + b;return *this; } bool operator < (const BigInteger& b)const { if(s.size() != b.s.size()) return s.size() < b.s.size(); for(int i = s.size()-1;i >= 0;i--){ if(s[i] != b.s[i]) return s[i] < b.s[i]; } return false; } bool operator > (const BigInteger& b)const { return b < *this; } bool operator <= (const BigInteger& b)const { return !(b < *this); } bool operator >= (const BigInteger& b)const { return !(*this < b); } bool operator != (const BigInteger& b)const { return b < *this || *this < b; } bool operator == (const BigInteger& b)const { return !(b < *this) && !(*this < b); } friend ostream& operator << (ostream &out,const BigInteger& x){ out << x.s.back(); for(int i = x.s.size() - 2; i >= 0;i--){ char buf[20]; sprintf(buf,"%08d",x.s[i]); for(int j = 0;j < strlen(buf);j++) out << buf[j]; } return out; } friend istream& operator >> (istream &in,BigInteger& x){ string s; if(!(in >> s)) return in; x = s; return in; } }; BigInteger dp[maxn][maxn],ans; inline BigInteger BigInt_max (BigInteger a, BigInteger b) { return a > b ? a : b; } int main(){ scanf("%d%d",&n,&m); for(int i = 1;i <= n;i++){ memset(dp,0,sizeof(dp)); for(int i = 1;i <= m;i++){ scanf("%d",&mapp[i]); dp[i][i] = mapp[i] << 1; } for(int len = 1;len < m;len++){ for(int l = 1;l <= m;l++){ int r = l + len; dp[l][r] = BigInt_max(dp[l+1][r] + mapp[l],dp[l][r-1] + mapp[r]) * 2; } } ans += dp[1][m]; } cout << ans; return 0; }
原文：https://www.cnblogs.com/bryce02/p/9895626.html
