玄关!记忆化搜索70pts求调。。。
查看原帖
玄关!记忆化搜索70pts求调。。。
1189047
Creeperawwman楼主2025/2/6 11:23

不知道为啥WA#7,#8,#9,求调求调ε(┬┬﹏┬┬)3

#include<bits/stdc++.h>
using namespace std;
const int maxn = 100;
int n, m;
int a[maxn];
struct gjd{//高精度部分写得太烂,不想看可以跳过(写的应该没问题吧。。。。。?)
	int len;
	int num[1010];
	gjd() {
		memset(num, 0, sizeof(num));
		len = 1;
	}
	void fla(int L) {
		len = L;
		for (int i = 1; i <= len; i++) {
			num[i + 1] += num[i] / 10;
			num[i] %= 10;
		}
		while (!num[len]) len--;
	}
	void operator=(const int &x) {
		len = 0;
		memset(num, 0, sizeof(num));
		int y = x;
		while (y != 0) {
			num[++len] = y % 10;
			y /= 10;
		}
	}
	void operator=(const gjd &x) {
		len = x.len;
		memset(num, 0, sizeof(num));
		for (int i = 1; i <= x.len; i++) num[i] = x.num[i];
	}
	gjd operator+(const gjd &x) {
		gjd an;
		int mlen = max(len, x.len);
		for (int i = 1; i <= mlen; i++) an.num[i] = num[i] + x.num[i];
		an.fla(mlen + 5);
		return an;
	}
	gjd operator*(const gjd &x) {
		gjd an;
		an.len = len + x.len;
		for (int i = 1; i <= len; i++) {
			for (int j = 1; j <= x.len; j++) {
				an.num[i + j - 1] += num[i] * x.num[j];
			}
		}
		an.fla(an.len + 2);
		return an;
	}
	gjd operator*(const int &x) {
		gjd an;
		for (int i = 1; i <= len; i++) an.num[i] = num[i] * x;
		an.fla(len + 12);
		return an;
	}
	bool operator<(const gjd &x) const {
		if (len == x.len) {
			for (int i = len; i >= 1; i--) {
				if (num[i] != x.num[i]) {
					return num[i] < x.num[i];
				}
			}
		}
		return len < x.len;
	}
	bool operator!=(const int &x) {
		if (x == 0 && num[1] == 0) return len != 0 && len != 1; 
		int y = x;
		int cnt = 0;
		for (int i = 1; y != 0; i++) {
			if (num[i] != y % 10) return true;
			y /= 10;
			cnt++;
		}
		return len != cnt;
	}
};
gjd ff[maxn][maxn];
gjd t[maxn];
void print(gjd x) {
	for (int i = max(x.len, 1); i >= 1; i--) cout<<x.num[i];
	cout<<endl;
}
gjd f(int l, int r, int cnt) {
	if (ff[l][r] != 0) return ff[l][r];
	ff[l][r] = max(f(l, r - 1, cnt + 1) + t[cnt] * a[r], f(l + 1, r, cnt + 1) + t[cnt] * a[l]);
	return ff[l][r];
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    gjd ans;
	t[0] = 1;
	for (int i = 1; i <= 80; i++) t[i] = t[i - 1] * 2;
	cin>>n>>m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin>>a[j];
			ff[j][j] = t[m] * a[j];
		}
		ans = ans + f(1, m, 1);
		for (int j = 1; j <= n; j++) {
			for (int k = 1; k <= m; k++) {
				ff[j][k] = 0;
			}
		}
	}
	print(ans);
    return 0;
}
2025/2/6 11:23
加载中...