P1005 [NOIP2007 提高组] 矩阵取数游戏
2023-12-13 18:53:02
网址: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数组的长度
累了累了,洗洗睡
题解就先不写了
补充:
先试了一下之前讲过的提高高精度效率的方法,对比我下面的代码就可以看出来,很明显的变化
代码如下:
#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));
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, first = 1; i >= 0; i--)
if(first)
{printf("%d", result[i]); first = 0;}
else
printf("%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的实现:我会专门写一篇博客来讲
文章来源:https://blog.csdn.net/Fool256353/article/details/134843676
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!