__int128采用记忆化递归为什么第二个点在本地上输出答案与标准一样还是错
查看原帖
__int128采用记忆化递归为什么第二个点在本地上输出答案与标准一样还是错
1093260
xiaochenlailou楼主2024/6/23 00:14
#include <bits/stdc++.h>
using namespace std;
const int MAX = 83;
int n, m;
__int128 a[MAX];
__int128 dp[MAX][MAX];
__int128 p[MAX];
__int128 sum = 0;

inline int read() { //快读
	int s = 0, w = 1;
	char ch = getchar();
//	while (ch < '0' || ch > '9') {if (ch == '-') {w = -1; ch = getchar();  /*读入的是负数*/	}}
	while (ch >= '0' && ch <= '9') {s = (s << 3) + (s << 1) + ch - '0';ch = getchar();}
	return s * w; //一定要乘以w,表示符号的意义
}

void print(__int128 x) {  //int128的特殊输出
	if (x > 9)
		print(x / 10);
	putchar(x % 10 + '0');
}

__int128 d(int x, int y) {
	if (dp[x][y] >= 0) return dp[x][y];
	if (y - x >= 1) dp[x][y] = max(a[x] * p[m - y + x] + d(x + 1, y), a[y] * p[m - y + x] + d(x, y - 1));  //函数递归调用的过程
	else dp[x][y] = a[x] * p[m - y + x]; //只剩下一个元素的时候
	return dp[x][y]; //返回一个值
} 

void solve() {
	cin >> n >> m;
//	n = read();
//	m = read();
	p[0] = 1;
	for (int i = 1; i <= m; i++)
		p[i] = 2 * p[i - 1];   //首先计算一下需要的2的各个次幂
	for (int i = 1; i <= n; i ++) {
		for (int j = 1; j <= m ; j++)
			a[j] = read();  //快读
//			cin >> a[j];
		memset(dp, -1, sizeof(dp)); //初始化一下
		sum += d(1, m); //每行独立求解
	}
	if (sum == 0)
		putchar('0');
	else
		print(sum); //int128输出最后的结果
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	solve();
	return 0;
}
2024/6/23 00:14
加载中...