ccf-csp 201809-4 再卖菜

Posted on | In | | Visitors:
Words count in article: 559

ccf-csp 201809-4 再卖菜

递推+回溯吧

已知第二天的的菜价，然后从第一个店铺开始依次尝试推到第一天的菜价即可（就是不断递推），递推发现不满足时就回溯修改，思路比较简单。

但是要做好剪枝，否则会超时！

我这里使用了一个flag[N][110][110]数组记录剪枝，flag[i][j][k]代表之前是否计算过第i个店铺价格为j且第i-1家店铺价格为k的情况（因为如果一旦相邻两个店铺的价格确定，后续店铺的情况就和之前讨论过的一样了，无需再次计算，肯定是不能求得解的），给flag[i][j][k]标记为true即可（说明曾经考虑过此情况，未能求得解）

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
#define N 310
int arr[N][2], ans[N], n;
bool flag[N][110][110];	// 用于记录剪枝
bool dfs(int nowIndex) {
	if (nowIndex == 1) {
		int end = min(arr[nowIndex][1] - 1, arr[nowIndex + 1][1] - 2);
		for (int i = 1; i <= end; i++) {
			ans[nowIndex] = i;
			if (dfs(nowIndex + 1))
				return true;
		}
	}
	else if(nowIndex < n){
		int start = arr[nowIndex - 1][0] - ans[nowIndex - 1] - ans[nowIndex - 2];
		int end = min(min(arr[nowIndex - 1][1] - ans[nowIndex - 1] - ans[nowIndex - 2], arr[nowIndex][1] - ans[nowIndex - 1] - 1), arr[nowIndex + 1][1] - 2);
		for (int i = max(start, 1); i <= end; i++) {
			if (flag[nowIndex][i][ans[nowIndex - 1]])
				continue;
			ans[nowIndex] = i;
			if (dfs(nowIndex + 1))
				return true;
			flag[nowIndex][i][ans[nowIndex - 1]] = true;
		}
	}
	else {
		int minTemp, maxTemp;
		minTemp = max(arr[nowIndex][0] - ans[nowIndex - 1], arr[nowIndex - 1][0] - ans[nowIndex - 1] - ans[nowIndex - 2]);
		maxTemp = min(arr[nowIndex][1] - ans[nowIndex - 1], arr[nowIndex - 1][1] - ans[nowIndex - 1] - ans[nowIndex - 2]);
		if (minTemp <= maxTemp && minTemp > 0) {
			ans[nowIndex] = minTemp;
			return true;
		}
	}
	return false;
}
int main() {
	memset(arr, 0, sizeof(arr));
	memset(ans, 0, sizeof(ans));
	memset(flag, 0, sizeof(flag));
	ios::sync_with_stdio(false), cin.tie(NULL);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i][0];
		if (i == 1 || i == n){
			arr[i][0] *= 2;	// 首尾两家店铺的最大最小值
			arr[i][1] = arr[i][0] + 1;
		}
		else {
			arr[i][0] *= 3;	// 中间店铺的最大最小值
			arr[i][1] = arr[i][0] + 2;
		}
	}
	dfs(1);
	for (int i = 1; i < n; i++)
		cout << ans[i] << " ";
	cout << ans[n] << endl;
	return 0;
}