题目链接：传送门
题目大意：
给定长度为m的数列aj，每次从两端取一个数，得到2k * aj的价值（k为当前的次数，从1开始到m），总共有n行这样的数列，求最大价值总和。
1 ≤ n, m ≤ 80, 0 ≤ aj ≤ 1000;
思路：
状态f[i][j]表示取剩下ai，ai+1，…，aj时的最大价值。
起始状态：
f[0][m-1] = 0；
转移方程：
f[i][j-1] = max(f[i][j-1], f[i][j] + 取掉aj得到的价值)；
f[i+1][j] = max(f[i+1][j], f[i][j] + 取掉ai得到的价值)；
PS：吃灰模板居然出了bug，还因此WA了一发，是时候更新一下高精模板了。
#include <bits/stdc++.h> using namespace std;
const int maxn = ;
const int MAX_N = + ; struct bigInt{
int len, d[maxn]; void clean() { while(len > && !d[len-]) len--; }
string str() const {
string s;
for (int i = ; i < len; i++) s += d[len--i] + '';
return s;
} bigInt() { memset(d, , sizeof d); len = ; }
bigInt(int num) { *this = num; }
bigInt(char* num) { *this = num; } bool operator < (const bigInt& b) const {
if(len != b.len)
return len < b.len;
for (int i = len-; i >= ; i--)
if (d[i] != b.d[i])
return d[i] < b.d[i];
return false;
}
bool operator >(const bigInt& b) const{return b < *this;}
bool operator<=(const bigInt& b) const{return !(b < *this);}
bool operator>=(const bigInt& b) const{return !(*this < b);}
bool operator!=(const bigInt& b) const{return b < *this || *this < b;}
bool operator==(const bigInt& b) const{return !(b < *this) && !(b > *this);} bigInt operator = (const char* num) {
memset(d, , sizeof d);
len = strlen(num);
for (int i = ; i < len; i++)
d[i] = num[len--i] - '';
clean();
return *this;
}
bigInt operator = (int num) {
char s[];
sprintf(s, "%d", num);
*this = s;
return *this;
}
bigInt operator + (const bigInt& b) {
bigInt c = *this;
for (int i = ; i < b.len; i++) {
c.d[i] += b.d[i];
c.d[i+] += c.d[i]/;
c.d[i] %= ;
}
c.len = max(len, b.len)+;
c.clean();
return c;
}
bigInt operator - (const bigInt& b) {
bigInt c = *this;
int i;
for (i = ; i < b.len; i++) {
c.d[i] -= b.d[i];
if (c.d[i] < ) c.d[i] += , c.d[i+]--;
}
while (c.d[i] < ) c.d[i++] += , c.d[i]--;
c.clean();
return c;
}//只能正数大减小
bigInt operator * (const bigInt& b) const {
bigInt c;
for (int i = ; i < len; i++)
for (int j = ; j < b.len; j++)
c.d[i+j] += d[i] * b.d[j];
for (int i = ; i < len+b.len || !c.d[i]; c.len = ++i) {
c.d[i+] += c.d[i] / ;
c.d[i] %= ;
}
c.clean();
return c;
}
bigInt operator / (const bigInt& b) {
bigInt c = *this, res = ;
for (int i = ; i < len; i++) {
res = res* + c.d[len--i];
int j;
for (j = ; j < ; j++)
if(res < b*(j+))
break;
c.d[len--i] = j;
res = res - b*j;
}
c.clean();
return c;
}
bigInt operator % (const bigInt& b) {
bigInt res = ;
for (int i = ; i < len; i++) {
res = res* + d[len--i];
int j;
for (j = ; j < ; j++)
if(res < b*(j+))
break;
res = res - b*j;
}
return res;
}
bigInt operator += (const bigInt& b) {
*this = *this + b;
return *this;
}
}; istream& operator >> (istream& in, bigInt& x)
{
string s;
in >> s;
x = s.c_str();
return in;
} ostream& operator << (ostream& out, const bigInt& x)
{
out << x.str();
return out;
} int N, M;
bigInt mat[MAX_N];
bigInt mul[MAX_N];
bigInt f[MAX_N][MAX_N]; bigInt dp()
{
bigInt cur;
for (int i = ; i < M; i++) {
for (int j = M-; j > i; j--) {
// cout << "f[" << i << "][" << j << "] = " << f[i][j] << ":" << endl;
// cout << "f[" << i << "][" << j-1 << "] = " << f[i][j-1] << ' ' << "f[" << i+1 << "][" << j << "] = " << f[i+1][j] << endl;
f[i][j-] = max(f[i][j-], f[i][j] + mul[M-(j-i+)+]*mat[j]);
f[i+][j] = max(f[i+][j], f[i][j] + mul[M-(j-i+)+]*mat[i]);
// cout << "f[" << i << "][" << j-1 << "] = " << f[i][j-1] << ' ' << "f[" << i+1 << "][" << j << "] = " << f[i+1][j] << endl;
}
}
for (int i = ; i < M; i++) {
cur = max(cur, f[i][i] + mul[M]*mat[i]);
}
// cout << cur << endl;
return cur;
} int main()
{
cin >> N >> M;
mul[] = ;
for (int i = ; i < MAX_N; i++)
mul[i] = mul[i-] * ;
bigInt ans;
while (N--) {
for (int i = ; i < M; i++) {
cin >> mat[i];
}
for (int i = ; i < M; i++)
for (int j = i; j < M; j++)
f[i][j] = ;
ans = ans + dp();
}
//模板居然出了bug，怕是在硬盘里吃灰吃多了
while (ans.d[ans.len-] > ) {
ans.d[ans.len] = ans.d[ans.len-] / ;
ans.d[ans.len-] %= ;
ans.len++;
}
cout << ans << endl;
return ;
}