DFS+减枝
从第一个商店一直搜到最后一个商店。
然后检查最后一个商店满不满足要求。
满足便输出,退出。(并保证是最小字典序)
C++ 代码
#include <iostream>
using namespace std;
const int N=307;
int n;
int day1[N];
int day2[N];
bool vis[N][N][N];//vis[x][y][z]:第一天第x个商店价格y且前一个价格为z
void dfs(int val,int u) { //第u个商店价格为val
//cout<<"u :"<<u<<" val :"<<val<<endl;
if(val<1||vis[u][val][day1[u-1]])return ;//减枝
else {
day1[u]=val;
vis[u][val][day1[u-1]]=true;
}
//分三种情况
if(u==1) {
dfs((day2[u]*2)-val,u+1);
dfs((day2[u]*2)-val+1,u+1);
} else if(u!=n) {
dfs((day2[u]*3)-val-day1[u-1],u+1);//和减去当前的,减去上一个,剩下的就是下一个位置的
dfs((day2[u]*3)-val-day1[u-1]+1,u+1);
dfs((day2[u]*3)-val-day1[u-1]+2,u+1);
} else {//到最后一个位置,验证结果是否正确
if(day2[u]==(day1[u]+day1[u-1])/2) {
for(int i=1; i<=n; i++)
cout<<day1[i]<<" ";
exit(0);//找到就退出
}
}
}
int main() {
cin>>n;
for(int i=1; i<=n; i++) {
cin>>day2[i];
}
for(int i=1; i<=207; i++)
dfs(i,1);//第一家商店价格最大200
return 0;
}