洛谷P1005 矩阵取数游戏
题意：
给一个n行m列的矩阵，m次取数，每次从n行中每一行取一个数（只能从每一行的首/尾取），每取一个数对应一个得分，每行取数的得分 = 被取走的元素值$ \times 2^i$，其中i表示第i次取数（从1开始编号）。求最大得分之和。
分析一下：
虽然题目给的是一个矩阵，但是各行互不影响，因此只需每行各自用dp求出本行最优解，然和相加就是总体最优解。
用M表示输入的矩阵的一行，M[i]表示该行第i个值
dp[i][j]表示区间变为[i,j]时的最优解
状态转移方程为： dp[i][j]=max(dp[i−1][j]+M[i−1]×2m−j+i−1，dp[i][j+1]+M[j+1]×2m−j+i−1)
终态是区间为空, dp[i][i]+M[i]×2m
两种方法：
- int128
#include <bits/stdc++.h>
using namespace std;
typedef __int128 lll;
void print(lll x) //__int128的I/O操作需手写
{
if (x == 0)
return;
if (x)
print(x / 10);
putchar(x % 10 + '0');
}
int n, m;
lll p[100] = {1}, dp[100][100] = {0};
int a[100] = {0};
lll fun()
{
for (int i = 1; i <= m; i++)
{
for (int j = m; j >= i; j--)
{
dp[i][j] = max(dp[i - 1][j] + p[m - j + i - 1] * a[i - 1], dp[i][j + 1] + p[m - j + i - 1] * a[j + 1]);
}
}
lll temp = -1;
for (int i = 1; i <= m; i++) //特殊情况，空区间
temp = max(temp, dp[i][i] + a[i] * p[m]);
return temp;
}
int main()
{
for (int i = 1; i <= 90; i++) //预处理2^i
p[i] = p[i - 1] << 1;
scanf("%d%d", &n, &m);
lll ans = 0;
while (n--)
{
for (int j = 1; j <= m; j++)
scanf("%d", a + j);
ans += fun();
}
if (ans == 0)
puts("0");
else
print(ans);
return 0;
}
PS:int128在Windows平台貌似是无法使用的，也就是说你无法在本地测试
- 高精度
#include <bits/stdc++.h>
using namespace std;
struct BigInteger
{
typedef unsigned long long LL;
static const int BASE = 100000000;
static const int WIDTH = 8;
vector<int> s;
BigInteger &clean()
{
while (!s.back() && s.size() > 1)
s.pop_back();
return *this;
}
BigInteger(LL num = 0) { *this = num; }
BigInteger(string s) { *this = s; }
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).clean();
}
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
{
assert(b <= *this); // 减数不能大于被减数
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 = s[i] + g;
if (i < b.s.size())
x -= b.s[i];
if (x < 0)
{
g = -1;
x += BASE;
}
else
g = 0;
c.s.push_back(x);
}
return c.clean();
}
BigInteger operator*(const BigInteger &b) const
{
int i, j;
LL g;
vector<LL> v(s.size() + b.s.size(), 0);
BigInteger c;
c.s.clear();
for (i = 0; i < s.size(); i++)
for (j = 0; j < b.s.size(); j++)
v[i + j] += LL(s[i]) * b.s[j];
for (i = 0, g = 0;; i++)
{
if (g == 0 && i >= v.size())
break;
LL x = v[i] + g;
c.s.push_back(x % BASE);
g = x / BASE;
}
return c.clean();
}
BigInteger operator/(const BigInteger &b) const
{
assert(b > 0); // 除数必须大于0
BigInteger c = *this; // 商:主要是让c.s和(*this).s的vector一样大
BigInteger m; // 余数:初始化为0
for (int i = s.size() - 1; i >= 0; i--)
{
m = m * BASE + s[i];
c.s[i] = bsearch(b, m);
m -= b * c.s[i];
}
return c.clean();
}
BigInteger operator%(const BigInteger &b) const
{ //方法与除法相同
BigInteger c = *this;
BigInteger m;
for (int i = s.size() - 1; i >= 0; i--)
{
m = m * BASE + s[i];
c.s[i] = bsearch(b, m);
m -= b * c.s[i];
}
return m;
}
int bsearch(const BigInteger &b, const BigInteger &m) const
{
int L = 0, R = BASE - 1, x;
while (1)
{
x = (L + R) >> 1;
if (b * x <= m)
{
if (b * (x + 1) > m)
return x;
else
L = x;
}
else
R = x;
}
}
BigInteger &operator+=(const BigInteger &b)
{
*this = *this + b;
return *this;
}
BigInteger &operator-=(const BigInteger &b)
{
*this = *this - b;
return *this;
}
BigInteger &operator*=(const BigInteger &b)
{
*this = *this * b;
return *this;
}
BigInteger &operator/=(const BigInteger &b)
{
*this = *this / b;
return *this;
}
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) && !(b > *this); }
};
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;
}
istream &operator>>(istream &in, BigInteger &x)
{
string s;
if (!(in >> s))
return in;
x = s;
return in;
}
int m, n;
const int maxm = 85;
BigInteger Weight[maxm];
inline void fun()
{
Weight[0] = 1;
for (int i = 1; i <= m; ++i)
{
Weight[i] = Weight[i - 1] * 2;
}
}
inline BigInteger MAX(const BigInteger &a,const BigInteger &b)
{
if (a < b)
return b;
return a;
}
int main()
{
scanf("%d%d", &n, &m);
fun();
BigInteger ans = 0, a[maxm];
while (n--)
{
BigInteger dp[maxm][maxm];
for (int i = 1; i <= m; ++i)
cin >> a[i];
for (int i = 1; i <= m; ++i)
for (int j = m; j >= i; --j)
dp[i][j] = MAX(dp[i - 1][j] + a[i - 1] * Weight[m - j + i - 1], dp[i][j + 1] + a[j + 1] * Weight[m - j + i - 1]);
BigInteger temp = 0;
for (int i = 1; i <= m; ++i)
temp = MAX(dp[i][i] + a[i]*Weight[m],temp);
ans += temp;
}
cout << ans << endl;
}
高精度实在是太慢了。。。这个代码在洛谷的评测机上最后一组数据会tle，开了O2优化才能通过。要用高精度写这个题还得找一个高效点的高精度板子
深信服三面1人在聊