没错 本龃龉又来水题解了
题目链接
题目大意
给你一个大小为n*m的矩阵，你将进行m次操作，每次操作可以拿矩阵中每一行两端的其中一个数字，每个数字只能拿一次。拿一个数字的贡献为该数字的权值 val×2^i (这个数是在第i次操作被拿走的)，然后问在m次操作后最大贡献和为多少。
思路
这道题就很像一个执行了n次的区间取数问题，那么我们可以用区间dp去解决。
dp[i][j] 中的i表示区间左端点，j表示区间又端点，dp[i][j] 整体表示当区间被取到 [i, j] 的时候的最优解。
那么我们看看怎么样写转移方程
因为区间 [i, j] 这个状态只能由 [i-1, j] 取走了左端点或者区间 [i, j+1] 取走了右端点才能到达，所以我们转移方程应该是：
（val[i]为i点的贡献值）
dp[i][j] = max(dp[i-1][j] + val[i], dp[i][j+1] + val[j]);
但是这道题的数据范围是 [1, 80] ， 2^80次方太大了，所以我们需要用大数取模拟这个过程。
大数模板
上代码！！！
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<map>
#define ll long long
#define pi acos(-1)
#define inf 0x3f3f3f3f
#define pii pair<int, int>
#define fi first
#define se second
#define l_son node<<1
#define r_son node<<1|1
#define mp(a, b) make_pair(a, b)
#define piii pair<pii, int>
#define uf(a, b, i) for (register int i = (a); i <= (b); ++i)
#define df(a, b, i) for (register int i = (a); i >= (b); --i)#define MAXN 9999
#define MAXSIZE 10
#define DLEN 4using namespace std;
inline int read() {
int x = 0, f = 1;char ch = getchar();while(ch < '0' || ch > '9') {
if(ch == '-') f = -1;ch = getchar();}while(ch >= '0' && ch <= '9') {
x = x * 10 + ch - '0';ch = getchar();}return x * f;
}
template<class T>
inline void print(T x) {
if(x > 9) print(x/10);putchar(x%10 + '0');
}
template<class T>
T Max(T a, T b) {
return a > b ? a : b;
}
template<class T>
T Min(T a, T b) {
return a < b ? a : b;
}
const ll mod = 1e9 + 7;class BigNum {
private:int a[500]; //可以控制大数的位数int len; //大数长度public:BigNum() {
len = 1; //构造函数memset(a,0,sizeof(a));}BigNum(const int); //将一个int类型的变量转化为大数BigNum(const BigNum &); //拷贝构造函数BigNum &operator=(const BigNum &); //重载赋值运算符，大数之间进行赋值运算friend istream& operator>>(istream&, BigNum&); //重载输入运算符friend ostream& operator<<(ostream&, BigNum&); //重载输出运算符BigNum operator+(const BigNum &) const; //重载加法运算符，两个大数之间的相加运算BigNum operator*(const BigNum &) const; //重载乘法运算符，两个大数之间的相乘运算bool operator>(const BigNum & T)const; //大数和另一个大数的大小比较};
BigNum::BigNum(const int b) {
//将一个int类型的变量转化为大数int c,d = b;len = 0;memset(a,0,sizeof(a));while(d > MAXN) {
c = d - (d / (MAXN + 1)) * (MAXN + 1);d = d / (MAXN + 1);a[len++] = c;}a[len++] = d;
}
BigNum::BigNum(const BigNum & T) : len(T.len) {
//拷贝构造函数int i;memset(a,0,sizeof(a));for(i = 0 ; i < len ; i++)a[i] = T.a[i];
}
BigNum & BigNum::operator=(const BigNum & n) {
//重载赋值运算符，大数之间进行赋值运算int i;len = n.len;memset(a,0,sizeof(a));for(i = 0 ; i < len ; i++)a[i] = n.a[i];return *this;
}
istream& operator>>(istream & in, BigNum & b) {
//重载输入运算符char ch[MAXSIZE*4];int i = -1;in>>ch;int l=strlen(ch);int count=0,sum=0;for(i=l-1; i>=0;) {
sum = 0;int t=1;for(int j=0; j<4&&i>=0; j++,i--,t*=10) {
sum+=(ch[i]-'0')*t;}b.a[count]=sum;count++;}b.len =count++;return in;}
ostream& operator<<(ostream& out, BigNum& b) {
//重载输出运算符int i;cout << b.a[b.len - 1];for(i = b.len - 2 ; i >= 0 ; i--) {
cout.width(DLEN);cout.fill('0');cout << b.a[i];}return out;
}BigNum BigNum::operator+(const BigNum & T) const {
//两个大数之间的相加运算BigNum t(*this);int i,big; //位数big = T.len > len ? T.len : len;for(i = 0 ; i < big ; i++) {
t.a[i] +=T.a[i];if(t.a[i] > MAXN) {
t.a[i + 1]++;t.a[i] -=MAXN+1;}}if(t.a[big] != 0)t.len = big + 1;elset.len = big;return t;
}
BigNum BigNum::operator*(const BigNum & T) const {
//两个大数之间的相乘运算BigNum ret;int i,j,up;int temp,temp1;for(i = 0 ; i < len ; i++) {
up = 0;for(j = 0 ; j < T.len ; j++) {
temp = a[i] * T.a[j] + ret.a[i + j] + up;if(temp > MAXN) {
temp1 = temp - temp / (MAXN + 1) * (MAXN + 1);up = temp / (MAXN + 1);ret.a[i + j] = temp1;} else {
up = 0;ret.a[i + j] = temp;}}if(up != 0)ret.a[i + j] = up;}ret.len = i + j;while(ret.a[ret.len - 1] == 0 && ret.len > 1)ret.len--;return ret;
}
bool BigNum::operator>(const BigNum & T) const {
//大数和另一个大数的大小比较int ln;if(len > T.len)return true;else if(len == T.len) {
ln = len - 1;while(a[ln] == T.a[ln] && ln >= 0)ln--;if(ln >= 0 && a[ln] > T.a[ln])return true;elsereturn false;} elsereturn false;
}
BigNum quick_pow(int pow) {
BigNum ans(1);BigNum a(2);while (pow) {
if (pow&1) ans = ans * a;a = a * a;pow /= 2;}return ans;
}
int n, m;
int rec[82][82];
BigNum dp[82][82];
BigNum f[82];
void scan() {
n = read();m = read();uf (1, n, i)uf (1, m, j)rec[i][j] = read();
}
void work() {
BigNum ans(0);f[1] = BigNum(2);uf (2, 80, i) f[i] = f[i-1] * f[1];uf (1, n, i) {
BigNum maxn(0);memset(dp, 0, sizeof(dp));uf (1, m, j) {
df (m, j, k) {
int pow = m-k+j-1;dp[j][k] = Max(dp[j-1][k]+BigNum(rec[i][j-1])*f[pow], dp[j][k+1]+BigNum(rec[i][k+1])*f[pow]);if (j == k) {
dp[j][k] = dp[j][k] + BigNum(rec[i][j])*f[m];maxn = Max(maxn, dp[j][k]);}}}ans = ans + maxn;}cout << ans << endl;
}
int main() {
scan();work();return 0;
}