201809-4（深搜暴力解决）

问题描述

试题编号：	201809-4
试题名称：	再卖菜
时间限制：	1.0s
内存限制：	256.0MB
问题描述：	问题描述　　在一条街上有n个卖菜的商店，按1至n的顺序排成一排，这些商店都卖一种蔬菜。　　第一天，每个商店都自己定了一个正整数的价格。店主们希望自己的菜价和其他商店的一致，第二天，每一家商店都会根据他自己和相邻商店的价格调整自己的价格。具体的，每家商店都会将第二天的菜价设置为自己和相邻商店第一天菜价的平均值（用去尾法取整）。　　注意，编号为1的商店只有一个相邻的商店2，编号为n的商店只有一个相邻的商店n-1，其他编号为i的商店有两个相邻的商店i-1和i+1。　　给定第二天各个商店的菜价，可能存在不同的符合要求的第一天的菜价，请找到符合要求的第一天菜价中字典序最小的一种。　　字典序大小的定义：对于两个不同的价格序列(a₁, a₂, ..., a_n)和(b₁, b₂, b₃, ..., b_n)，若存在i (i>=1), 使得a_i<b_i，且对于所有j<i，a_j=b_j，则认为第一个序列的字典序小于第二个序列。输入格式　　输入的第一行包含一个整数n，表示商店的数量。　　第二行包含n个正整数，依次表示每个商店第二天的菜价。输出格式　　输出一行，包含n个正整数，依次表示每个商店第一天的菜价。样例输入 8 2 2 1 3 4 9 10 13 样例输出 2 2 2 1 6 5 16 10 数据规模和约定　　对于30%的评测用例，2<=n<=5，第二天每个商店的菜价为不超过10的正整数；　　对于60%的评测用例，2<=n<=20，第二天每个商店的菜价为不超过100的正整数；　　对于所有评测用例，2<=n<=300，第二天每个商店的菜价为不超过100的正整数。　　请注意，以上都是给的第二天菜价的范围，第一天菜价可能会超过此范围。

解题思路：由于本体的数据不大，可以直接暴力搜索，所以试了一下，结果过了

首先枚举了第一天的所有情况，由于数据都是从小到大，所以第一个满足条件的必定时最小解了

第一天分两种情况（因为第一天时两天求和的结果），之后的2到n-1天都是三种结果，最后一天单独判断

直接暴力深搜，满足条件的话输出数组

代码如下

#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <algorithm>
#include <fstream>
using namespace std;


///201809

int a[500],b[500];  //输入菜价所求菜价
int f[305][305][305];
int num;
void dfs(int n,int x,int y)     //n表示第n个点，x表示第n-1天的报价，y表示所给的第n天的报价
{
    if(f[n][x][y])  return;
    f[n][x][y]=1;
    if(n==num)
    {
        if((x+y)/2==a[n])　　　　　　//最后一点直接判断，不用分情况讨论，这里卡了好几次

        {
            cout<<b[1];
            for(int i=2;i<=num;i++)
                cout<<" "<<b[i];
            exit(0);
        }
    }
    for(int i=0;i<3;i++)
    {
        b[n+1]=3*a[n]-x-y+i;
        if(b[n+1]>=1)
            dfs(n+1,y,b[n+1]);
    }
}

int main()
{
    freopen("in.txt","r",stdin);
    cin>>num;
    for(int i=1;i<=num;i++)
    {
        cin>>a[i];
    }
    for(int i=1;i<=2*a[1];i++)//第一天的报价从小到大
    {
        b[1]=i;
        b[2]=2*a[1]-i;    //第二天菜价分两种情况
        if(b[2]>0)  dfs(2,i,b[2]);
        b[2]=2*a[1]-i+1;
        if(b[2]>0)  dfs(2,i,b[2]);
    }
    return 0;
}