题目困扰了我很久，后来才知道，该怎么解题。
这题说是说矩阵取数，但是仔细看看能够知道，和矩阵没什么关系，只每行的最大值有关，因为每行之间的最大没有任何关系。那么就将矩阵取数转变成了对数组取数，对数组取数很容易看出来是DP，DP方程如下：f[i][j] = max( 2 map[i] + 2 f[i + 1][j], 2 map[j] + 2 f[i][j – 1] )。最初状态是f[i][i] = 2 map[i]。f[i][j]的是i~j之间的能够取的最大值。
方程我还解释一下，比如第一个数据吧：
就是这样的思路，其实思路我三天前就有了，但是因为数据太大，2^80以上，用long long 都装不下，那只能使用高精度了，但是实在很难下手啊
。怎么办？没办法了，只好先用int来写，然后封装起来，再把int改成高精度，啥？这句话没看懂？
意思就是说我先写了下面第一段代码，没用高精度，只得了40分，但是下面这个代码的框架封装的很好，然后直接将几个函数修改一下就能够使用高精度了：
#include <stdio.h>
#include <string.h>
/ ===============对使用"数"类型的封装=============== /
typedef struct{
int num;
}num;
void give(num a, int n)
{
a->num = n;
}
void add(num a, num b)
{
a->num += b->num;
}
void addnum(num a, int n)
{
a->num += n;
}
void copy(num a, num b)
{
a->num = b->num;
}
int compare(num a, num b)
{
return a->num – b->num;
}
void output(num a)
{
printf("%d\n", a->num);
}
/ ===============程序的实现=============== /
num f[80][80];
num ans;
num s1, s2;
int map[80];
void srch(int n)
{
int i, k;
num t;
memset(f, 0, sizeof(f));
for(i = 0; i < n; i++){
give(&f[i][i], map[i]);
addnum(&f[i][i], map[i]);
}
for(k = 1; k < n; k++){
for(i = 0; i < n – k; i++){
copy(&s1, &f[i + 1][i + k]);
addnum(&s1, map[i]);
copy(&s2, &f[i][i + k – 1]);
addnum(&s2, map[i + k]);
if(compare(&s1, &s2) < 0){
t = &s2;
}else{
t = &s1;
}
copy(&f[i][i + k], t);
add(&f[i][i + k], t);
}
}
}
int main(void)
{
int m, n;
int i, j;
memset(&ans, 0, sizeof(ans));
scanf("%d%d", &n, &m);
for(i = 0; i < n; i++){
for(j = 0; j < m; j++){
scanf("%d", &map[j]);
}
srch(m);
add(&ans, &f[0][m – 1]);
}
output(&ans);
return 0;
}
高精度的代码等下发上来。
#include <string.h>
#include <math.h>
/ =====================高精度实现部分===================== /
#define max(a, b) ((a)>(b)?(a):(b))
#define TOTAL 40
const int used = 100000000;
#define bits ((int)log10(used))
typedef struct{
int num[TOTAL];
int len;
}num;
static void deal(num a)
//防止高精度的漏洞.
//如:used = 10000, give(a, 10000), give(a, 1), give(b, 10000), add(a, b)
//此时a为20001而不是10001
{
int i;
for(i = a->len; i < TOTAL; i++){
a->num[i] = 0;
}
}
void give(num a, int n)
{
int i;
for(i = 0; n; i++){
a->num[i] = n % used;
n /= used;
}
a->len = i;
deal(a);
}
void add(num a, num b)
//这里有个bug, a和b 不能相同
{
int i;
int len = max(a->len, b->len);
int re = 0;
for(i = 0; i < len; i++){
a->num[i] += b->num[i] + re;
re = a->num[i] / used;
if(re > 0){
a->num[i] %= used;
}
}
a->len = len;
if(re > 0){
a->len++;
a->num[i] = re;
//掉了 a->num[i] = re; 这一行
}
}
void addnum(num a, int n)
{
int i;
int re = 0;
for(i = 0; n; i++){
a->num[i] += (n % used) + re;
n /= used;
re = a->num[i] / used;
if(re > 0){
a->num[i] %= used;
}
}
a->len = max(i, a->len);
if(re > 0){
a->num[i] += re;
//写成了=re;
a->len = max(i + 1, a->len);
}
}
void copy(num a, num b)
{
memcpy(a, b, sizeof(num));
}
int compare(num a, num b)
{
if(a->len != b->len){
return a->len – b->len;
}
int i;
for(i = a->len – 1; i >= 0; i–){
//是i–不是i++
if(a->num[i] != b->num[i]){
return a->num[i] – b->num[i];
}
}
return 0;
return a->num – b->num;
}
void output(num a)
{
int i;
int len = a->len, num = a->num;
printf("%d", num[len – 1]);
len–;
for(i = len – 1; i >= 0; i–){
printf("%.d", bits, num[i]);
}
printf("\n");
}
/ =====================主函数部分===================== /
num f[80][80];
num ans;
num s1, s2;
int map[80];
void srch(int n)
{
int i, k;
num t;
memset(f, 0, sizeof(f));
for(i = 0; i < n; i++){
give(&f[i][i], 2 * map[i]);
}
for(k = 1; k < n; k++){
for(i = 0; i < n – k; i++){
copy(&s1, &f[i + 1][i + k]);
addnum(&s1, map[i]);
copy(&s2, &f[i][i + k – 1]);
addnum(&s2, map[i + k]);
if(compare(&s1, &s2) < 0){
t = &s2;
}else{
t = &s1;
}
copy(&f[i][i + k], t);
add(&f[i][i + k], t);
}
}
}
int main(void)
{
int m, n;
int i, j;
memset(&ans, 0, sizeof(ans));
scanf("%d%d", &n, &m);
for(i = 0; i < n; i++){
for(j = 0; j < m; j++){
scanf("%d", &map[j]);
}
srch(m);
add(&ans, &f[0][m – 1]);
}
output(&ans);
return 0;
}