关于 dp 前处理的一些问题
查看原帖
关于 dp 前处理的一些问题
128591
Refined_heart楼主2022/7/3 21:20

如题,萌新学习了第 33 篇题解的做法,但是发现,代码中注释掉的两句话来替换掉未注释的相邻语句后结果是不一致的,而这和预期不符,想请问一下原因是什么。

具体地,题解中的处理是将所有 >h1>h_1 的数提出来然后都减掉了 h1h_1 并从大于 h1h_1 的开始 dp.dp. 我不理解的地方有两个:

  • 为什么少了减掉 h1h_1 的部分答案会错?(目前怀疑是精度但是并没有改出来错)

  • 为什么在前面多补一个 00 也就是 dpdpb0b_0 开始,为什么也是对的?

代码如下:

namespace Refined_heart {
	const int N = 2e5 + 10;
	int n, k, pp;
	int h[N];
	Decimal a[N];
	namespace Sub1 {
		Decimal dfs(int now) {
			if(now == k + 1) return a[1];
			Decimal Ans = 0;
			for(int i = 1; i < (1 << (n)); ++i) {
				Decimal sum = 0;
				int cnt = 0; 
				for(int j = 0; j < n; ++j) {
					if(!(i >> j & 1)) continue;
					sum += a[j + 1]; cnt = cnt + 1; 
				}
				Decimal hh[5];
				for(int j = 1; j <= n; ++j) hh[j] = a[j];
				sum /= cnt;
				for(int j = 0; j < n; ++j) {
					if(!(i >> j & 1)) continue;
					a[j + 1] = sum;
				}
				Decimal nxtans = dfs(now + 1); 
				if(Ans < nxtans) Ans = nxtans;
				for(int j = 1; j <= n; ++j) a[j] = hh[j];
			}
			return Ans;
		}
		void solve() {
			Decimal Ans = dfs(1);
			cout << Ans.to_string(pp + pp) << '\n';
		}
	}
	long double f[2][8001], b[50001], sum[100001];
	int pre[8001][8001], qid[8001];
	struct pt {
		double x, y;
		pt(double x_ = 0, double y_ = 0) {
			x = x_; y = y_;
		}
	} p[N], q[N];
	pt operator - (pt x, pt y) {return pt(x.x - y.x, x.y - y.y);}
	long double operator ^ (pt x, pt y) {return x.x * y.y - x.y * y.x;}
	Decimal getans(int x, int y) {
		if(x == 0) return 0;
		return (getans(x - 1, pre[x][y]) + (double)sum[y] - (double)sum[pre[x][y]]) / (y - pre[x][y] + 1);
	}
	void solve() {
		cin >> n >> k >> pp;
		for(int i = 1; i <= n; ++i) cin >> h[i];
		sort(h + 2, h + n + 1);
		reverse(h + 2, h + n + 1);
		for(int i = 1; i <= n; ++i) a[i] = h[i];
		double Base = h[1];
		if(k == 1) {
			Decimal pre = a[1];
			Decimal sum = a[1];
			for(int i = 2; i <= n; ++i) {
				Decimal now = sum + a[i];
				now = now / i;
				if(now > pre) {
					pre = now; 
					sum = sum + a[i];
				}
				else {
					break;
				}
			}
			cout << pre.to_string(pp + pp) << '\n';
			return ;
		}
		if(k >= n) {
			reverse(a + 2, a + n + 1);
			for(int i = 2; i <= n; ++i) {
				if(a[i] < a[1]) continue;
				Decimal now = a[1] + a[i];
				now = now / 2;
				a[i] = a[1] = now;
			}
			Decimal ans = a[1];
			cout << ans.to_string(pp + pp) << '\n';
			return ;
		}
		int cnt = 0;
		b[++cnt] = Base;
		for(int i = 1; i <= n; ++i) if(a[i] > Decimal(Base)) b[++cnt] = a[i].to_double();
		sort(b + 1, b + cnt + 1);
//		for(int i = 1; i <= cnt; ++i) b[i] = b[i] - Base;
		for(int i = 1; i <= cnt; ++i) sum[i] = sum[i - 1] + b[i];
		Decimal Ans = Decimal("0");
		n = cnt;
		double ans = 0, pos = 0; 
		for(int t = 1; t <= k; ++t) {
			int head = 1, tail = 0; 
			int now = t & 1; qid[1] = t - 1;
			int i = t; 
			q[++tail] = pt(i - 2, sum[i - 1] - f[now ^ 1][i - 1]); 
			for(int j = i; j <= n; ++j) {
				pt P = pt(double(j), sum[j]);
				while(head < tail && ((q[head] - P) ^ (q[head + 1] - P)) > 0) ++head;
				pre[i][j] = qid[head]; 
				f[now][j] = (P.y - q[head].y) / (P.x - q[head].x);
				P = pt(j - 1, sum[j] - f[now ^ 1][j]);
				while(head < tail && ((P - q[tail]) ^ (P - q[tail - 1])) > 0) --tail;
				qid[++tail] = j; q[tail] = P;
			}
			if(f[now][n] >= ans) {
				ans = f[now][n];
				pos = i;
			}
		}
		Ans = getans(pos, n); 
//		Ans = getans(pos, n) + Decimal(Base); 
		cout << Ans.to_string(pp * 6 / 5 + 1) << '\n';
	}
}
signed main() {
	Refined_heart :: solve();
	return 0;
}
2022/7/3 21:20
加载中...