网址：P1005 [NOIP2007 提高组] 矩阵取数游戏 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

动态规划和高精度的组合，使我的滨州旋转

最后只得了80，两个测试点超时了

看题解有人是用了int128来做的，明天学一下

我的递归思路和常规的不同，但也能做就是了，明天参考一下他们的

垃圾代码如下：

#include<stdio.h>
#include<string.h>
#define MAXN 30
void multiply_constant(int a[], int b);
void add_constant(int a[], int b);
void add_array(int a[], int b[]);
int digcmp(int a[], int b[]);
int diglen(int a[]);
int dp[81][81][MAXN], num[81], result[MAXN];
int n, m;//result的长度int main(void)
{scanf("%d%d", &n, &m);for(int i = 0; i < n; i++){memset(dp, 0, sizeof(dp));for(int j = 1; j <= m; j++)scanf("%d", &num[j]);for(int j = 1; j <= m; j++){add_constant(dp[0][j], num[m + 1 - j]), add_constant(dp[j][0], num[j]);for(int k = 0; k < j; k++)multiply_constant(dp[0][j], 2), multiply_constant(dp[j][0], 2);add_array(dp[0][j], dp[0][j - 1]), add_array(dp[j][0], dp[j - 1][0]);}//处理一直从左边取和一直从右边取的情况for(int j = 2; j <= m; j++)//j代表取了多少数{for(int x = 1; x < j; x++){int y = j - x;int tmp1[MAXN] = {0}, tmp2[MAXN] = {0};add_constant(tmp1, num[x]), add_constant(tmp2, num[m + 1 - y]);for(int k = 0; k < j; k++)multiply_constant(tmp1, 2), multiply_constant(tmp2, 2);add_array(tmp1, dp[x - 1][y]), add_array(tmp2, dp[x][y - 1]);if(digcmp(tmp1, tmp2) >= 0)memcpy(dp[x][y], tmp1, sizeof(tmp1));elsememcpy(dp[x][y], tmp2, sizeof(tmp2));}//dp[x][y] = max{dp[x - 1][y] + num[x] * 2 ^ j, dp[x][y - 1] + num[m + 1 - y] * 2 ^ j}//x代表左边取了多少数，y代表右边取了多少数}//得到取完的数中的最大的数int tmp[MAXN] = {0};for(int x = 0; x <= m; x++){int y = m - x;if(digcmp(tmp, dp[x][y]) < 0)memcpy(tmp, dp[x][y], sizeof(dp[x][y]));}//result加上最大的数add_array(result, tmp);}//输出resultfor(int i = diglen(result) - 1; i >= 0; i--)printf("%d", result[i]);return 0;
}
void multiply_constant(int a[], int b)
{int ext = 0, i;for(i = 0; i < diglen(a); i++){ext += b * a[i];a[i] = ext % 10;ext /= 10;}while(ext){a[i++] = ext % 10;ext /= 10;}return;
}
void add_constant(int a[], int b)
{int ext = 0, i = 0;while(b){ext += a[i] + b % 10;a[i++] = ext % 10;ext /= 10, b /= 10;}return;
}
void add_array(int a[], int b[])
{int ext = 0;for(int i = 0; i < MAXN; i++){ext += a[i] + b[i];a[i] = ext % 10;ext /= 10;}return;
}//m加到n上
int digcmp(int a[], int b[])
{for(int i = MAXN - 1; i >= 0; i--)if(a[i] != b[i])return a[i] - b[i];return 0;
}//n更大时返回整数
int diglen(int a[])
{int i;for(i = MAXN; i >= 0; i--)if(a[i])  break;if(i < 0) return 1;return i + 1;
}//得到n数组的长度

累了累了，洗洗睡

题解就先不写了

补充：

先试了一下之前讲过的提高高精度效率的方法，对比我下面的代码就可以看出来，很明显的变化

代码如下：

#include<stdio.h>
#include<string.h>
#define MAXN 25
void multiply_constant(int a[], int b);
void add_constant(int a[], int b);
void add_array(int a[], int b[]);
int digcmp(int a[], int b[]);
int diglen(int a[]);
int dp[81][81][MAXN], num[81], result[MAXN];
int n, m;//result的长度int main(void)
{scanf("%d%d", &n, &m);for(int i = 0; i < n; i++){memset(dp, 0, sizeof(dp));for(int j = 1; j <= m; j++)scanf("%d", &num[j]);for(int j = 1; j <= m; j++){add_constant(dp[0][j], num[m + 1 - j]), add_constant(dp[j][0], num[j]);for(int k = 0; k < j; k++)multiply_constant(dp[0][j], 2) , multiply_constant(dp[j][0], 2);add_array(dp[0][j], dp[0][j - 1]), add_array(dp[j][0], dp[j - 1][0]);}//处理一直从左边取和一直从右边取的情况for(int j = 2; j <= m; j++)//j代表取了多少数{for(int x = 1; x < j; x++){int y = j - x;int tmp1[MAXN] = {0}, tmp2[MAXN] = {0};add_constant(tmp1, num[x]), add_constant(tmp2, num[m + 1 - y]);for(int k = 0; k < j; k++)multiply_constant(tmp1, 2), multiply_constant(tmp2, 2);add_array(tmp1, dp[x - 1][y]), add_array(tmp2, dp[x][y - 1]);if(digcmp(tmp1, tmp2) >= 0)memcpy(dp[x][y], tmp1, sizeof(tmp1));elsememcpy(dp[x][y], tmp2, sizeof(tmp2));}//dp[x][y] = max{dp[x - 1][y] + num[x] * 2 ^ j, dp[x][y - 1] + num[m + 1 - y] * 2 ^ j}//x代表左边取了多少数，y代表右边取了多少数}//得到取完的数中的最大的数int tmp[MAXN] = {0};for(int x = 0; x <= m; x++){int y = m - x;if(digcmp(tmp, dp[x][y]) < 0)memcpy(tmp, dp[x][y], sizeof(dp[x][y]));}//result加上最大的数add_array(result, tmp);}//输出resultfor(int i = diglen(result) - 1, first = 1; i >= 0; i--)if(first){printf("%d", result[i]);  first = 0;}elseprintf("%09d", result[i]);return 0;
}
void multiply_constant(int a[], int b)
{int ext = 0, i;for(i = 0; i < diglen(a); i++){ext += b * a[i];a[i] = ext % 1000000000;ext /= 1000000000;}while(ext){a[i++] = ext % 1000000000;ext /= 1000000000;}return;
}
void add_constant(int a[], int b)
{int ext = 0, i = 0;while(b){ext += a[i] + b % 1000000000;a[i++] = ext % 1000000000;ext /= 1000000000, b /= 1000000000;}return;
}
void add_array(int a[], int b[])
{int ext = 0;for(int i = 0; i < MAXN; i++){ext += a[i] + b[i];a[i] = ext % 1000000000;ext /= 1000000000;}return;
}//m加到n上
int digcmp(int a[], int b[])
{for(int i = MAXN - 1; i >= 0; i--)if(a[i] != b[i])return a[i] - b[i];return 0;
}//n更大时返回整数
int diglen(int a[])
{int i;for(i = MAXN - 1; i >= 0; i--)if(a[i])  break;if(i < 0) return 1;return i + 1;
}//得到n数组的长度

这样得了90分，最后一个测评点就超了一点时

只要把long long换成int，然后改一下一格储存的数据上限就可以拿到满分了

这是最简单的高精度优化方式

还有一个优化方式，就是不要一次一次地乘2，在不会溢出的情况下，改成一次乘2^n，然后满足需要求的数，如要乘2^80次方，可以先乘2^20次方，然后乘下去

但是要注意，因为我已经尽量地利用int储存的空间了，所以可以乘的2^n的n是相对较小的，两个方法算是鱼和熊掌不可兼得

然后是其他的dp方法：

一般的是区间dp法：即当剩余数的区间在[ai, aj]的时候的最大值

还有另一个方法：先从中间开始取，每dp一次就将数加上新的数乘2，这样计算会比较简单（在用到高精度数组的情况下）

最后是int128的实现：我会专门写一篇博客来讲