P1005 [NOIP2007 提高组] 矩阵取数游戏

网址：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));
                else
                    memcpy(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);
    }
    //输出result
    for(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数组的长度

累了累了，洗洗睡

题解就先不写了