问题描述：

解题思路：

已知a[n],求b[n]，其中a[n]是所给数据，b[n]是要求的菜价

其中有 (b[n-1]+b[n]+b[n+1])/3=a[n]（n表示第n天菜价）

所以b[n+1]=3*a[n]-b[n-1]-b[n]，或b[n+1]=3*a[n]-b[n-1]-b[n]+1，或b[n+1]=3*a[n]-b[n-1]-b[n]+2

递推关系式就求出来了，每次用b[n-1],b[n],得出b[n+1]，所以用dfs暴搜

这里要考虑特殊情况，就是第一天和最后一天是除以2，所以写两种情况就可以了

加上“剪枝” 能大幅度降低复杂度~~~

解题代码：

#include <bits/stdc++.h>
using namespace std;
const int P = 100 + 5;
const int N = 300 + 1;
int n, a[N], b[N], vis[N][P][P];
void dfs(int d){if (d == n + 1) {if (b[n] != (a[n-1] + a[n]) / 2) return;cout << a[1];for (int i = 2; i <= n; i++)cout << " " << a[i];cout << endl;exit(0);} else {for (a[d] = 3 * b[d - 1] - a[d - 1] - a[d - 2];a[d] <= 3 * b[d - 1] + 2 - a[d - 1] - a[d - 2]; a[d]++)if (a[d] > 0 && vis[d][a[d]][a[d - 1]] == 0) {vis[d][a[d]][a[d - 1]] = 1;dfs(d + 1);}}
}
int main(){std::ios::sync_with_stdio(false);std::cin.tie(NULL);cout.tie(NULL);cin >> n;for (int i = 1; i <= n; i++) cin >> b[i];memset(vis, 0, sizeof vis);for(a[1] = 1; a[1] <= 2 * b[1]; a[1]++)for(a[2] = 2 * b[1] - a[1]; a[2] <= 2 * b[1] + 1 - a[1]; a[2]++)if (a[2] > 0) dfs(3);return 0;
}