CCF201809第四题再卖菜C++100分回溯法通俗易懂
自己练习做的，用的是回溯法，上面那个三维数组是精髓，减少了程序运行时间，从80分到了100分.
作者：best小小周
考了两次CCF，都是200分，在追逐400分的路上，下面分享一下这个第四题再卖菜的思路。小白一个，代码会有很多傻傻的地方，请大家多包容。
首先附上题干
这个题主要是推测第一天的商店的价格。我简单的读了一下这个题，在纸上画了一画。这个题感觉思路还是蛮清晰的。首先，有两个特殊情况，一个是第一次，一个是最后一次。这两次都是两个商店的平均，所以我们就把他拿出来。其他的都是三个平均。把其他的放在一起。这个题大概就是知道前两天，可以推测第三天的价格范围（上下浮动3元，读题干分析很容易知道）前两天的价格我们可以把所有可能有写出来。对于这个题首先想到的就是递归，当成功的时候就输出，不成功就break，返回。
其实我也是后来才知道，这个方法叫做回溯法（以前上数据结构的时候学过思路，就是不记得名字。）就是我下面代码的getNextPrice函数，通过这个函数递归，直到最后两个。因为题干要求的是取字典序最小定义。其实就是让前面的尽可能小，我们才有for循环，从小往大，一遇到符合条件的，程序就结束，就符合这个最小定义。
其实这个题80分不难，难的是100分。这个题的精髓其实只有一句就是：
if (isUsed[num + 1][nowPrice][nextPrice]) { continue; }
这个是记录重复的递归函数，如果被记录，代表这种情况之前已经计算过，但是没有成功，我们添加这个条件，就可以大幅度的降低程序的运行时间。
下面是完整的代码，在C++11运行。（C++11有一个很好的东西，那就是to_string。）
#include
#include
using namespace std;
int n;
int storeP[300];
int nowP[300];
int store3P[300];
bool isUsed[300][300][300] = { false };
int getNextPrice(int num, int lastPrice,int nowPrice) {//通过前两个的价格得到下一个价格
isUsed[num][lastPrice][nowPrice] = true;
int nextPrice = 0;
int sym=0;
if (num == n - 1) {//循环终止条件，当到最后一个的时候判断是否满足条件。满足sym标记为1.
if ((nowPrice + lastPrice) / 2 == storeP[num]) {
nowP[num] = nowPrice;
sym = 1;
}
}
else {
int nPrice = store3P[num] - lastPrice - nowPrice;
for (int i = 0; i < 3; i++)//这个是通过分析得到的，下一个商店的价格有三种可能。简单循环就可以
{
nextPrice=nPrice+i;
if (nextPrice < -1) { break; }
if (nextPrice > n;
for (int i = 0; i > price;
storeP[i] = price;
store3P[i] = 3 * price;
}
for (int i = 1; i <= storeP[0] *2; i++)
{
int nowprice = i;
if (i != storeP[0] * 2) {
int nextprice1 = storeP[0] * 2 - i;
if (getNextPrice( 1, nowprice, nextprice1))
{
nowP[0] = nowprice;
break;
}
}
int nextprice2 = storeP[0] * 2 - i + 1;
if (getNextPrice( 1, nowprice, nextprice2)) {
nowP[0] = nowprice;
break;
}
}
for (int i = 0; i < n; i++)
{
cout << nowP[i] << " ";
}
return 0;
}
作者：best小小周