__int128 + 记忆化求助
查看原帖
__int128 + 记忆化求助
1118614
I_Love_DS楼主2024/7/23 08:35
#include <bits/stdc++.h>
using namespace std;
int n, m, a[85][85], dp[85][85];
__int128 ans = 0;
__int128 solve(int s, int l, int r, int pw) {
	if (dp[l][r]) return dp[l][r];
	if (l >= r) {
		dp[l][r] = ((__int128)(1) << pw) * a[s][l];
		return dp[l][r];
	}
	//printf("%d %d\n", l, r);
	dp[l][r] = max(solve(s, l + 1, r, pw + 1) + ((__int128)(1) << pw) * a[s][l], solve(s, l, r - 1, pw + 1) + ((__int128)(1) << pw) * a[s][r]);
	return dp[l][r];
}
void print(__int128 out, bool is) {
	if (out) print(out / 10, 1);
	else if (!out && !is) {
		printf("0");
		return;
	}
	else return;
	printf("%d", (int)(out % 10));
}
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) 
		for (int j = 1; j <= m; j++) 
			scanf("%d", &a[i][j]);
	for (int s = 1; s <= n; s++) {
		memset(dp, 0, sizeof(dp));
		ans += solve(s, 1, m, 1);
	}
	print(ans, 0);
	return 0;
}

记录

2024/7/23 08:35
加载中...