dp60求调
查看原帖
dp60求调
1272259
cgxd楼主2024/10/26 21:28
#include<bits/stdc++.h>
using namespace std;
int n, m, a[85];
long double ans, f[85][85];
vector<long double> p{1.l};
long double dp(){
	memset(f, 0, sizeof(f));
	for(int i = 1; i <= m; ++i)
		for(int j = m; j >= i; --j)
			f[i][j] = max(f[i - 1][j] + p[m - j + i - 1] * a[i - 1], f[i][j + 1] + p[m - j + i - 1] * a[j + 1]);
	long double maxn = 0;
	for(int i = 1; i <= m; ++i) maxn = max(maxn, f[i][i] + a[i] * p[m]);
    return maxn;
}signed main(){
	for(int i = 1; i <= 85; ++i) p.push_back(p.back() * 2);
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; ++i){
		for(int j = 1; j <= m; ++j)
			scanf("%d", &a[j]);
		ans += dp();
	}printf("%.0Lf", ans);
	return 0;
}
2024/10/26 21:28
加载中...