CCF 再卖菜 100分

﹏ヽ暗。殇╰゛Y 2023-07-10 12:52 1阅读 0赞

![20200302173152333.png][]

# 关于怎么从40分---->70分----->100分，我在代码里面的注释部分都写明了。 #

问题描述

在一条街上有n个卖菜的商店，按1至n的顺序排成一排，这些商店都卖一种蔬菜。  
　　第一天，每个商店都自己定了一个正整数的价格。店主们希望自己的菜价和其他商店的一致，第二天，每一家商店都会根据他自己和相邻商店的价格调整自己的价格。具体的，每家商店都会将第二天的菜价设置为自己和相邻商店第一天菜价的平均值（用去尾法取整）。  
　　注意，编号为1的商店只有一个相邻的商店2，编号为n的商店只有一个相邻的商店n-1，其他编号为i的商店有两个相邻的商店i-1和i+1。  
　　给定第二天各个商店的菜价，可能存在不同的符合要求的第一天的菜价，请找到符合要求的第一天菜价中字典序最小的一种。  
　　字典序大小的定义：对于两个不同的价格序列(a1, a2, ..., an)和(b1, b2, b3, ..., bn)，若存在i (i>=1), 使得ai<bi，且对于所有j<i，aj=bj，则认为第一个序列的字典序小于第二个序列。

输入格式

输入的第一行包含一个整数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的正整数。  
　　请注意，以上都是给的第二天菜价的范围，第一天菜价可能会超过此范围。

#include<iostream>
    #include<algorithm>
    #include<string>
    #include<vector>
    #include<queue>
    #include<map>
    #include<unordered_map>
    #include<set>
    #include<sstream>
    using namespace std;
    const int MAXN = 305; 
    
    int n;  //一共有n家店 
    int ans[MAXN] = {-1,-1};  //最终的答案 （第一天的菜价） 
    int a[MAXN];  //第一天的菜价 （临时的） 
    int b[MAXN];  //第二天的菜价 
    
    void replace(){  //根据字典序进行替换 
    	bool flag = false;
    	if(ans[1] == -1){
    		flag = true;
    	}else{
    		for(int i=1;i<=n;i++){
    			if(a[i] < ans[i]){
    				flag = true;
    				break;
    			}else if(a[i] > ans[i]){
    				break;
    			}
    		}
    	}
    	if(flag){
    		for(int i=1;i<=n;i++){
    			ans[i] = a[i];
    		}
    	}
    }
    
    //进行剪枝，没有rem数组进行剪枝的话会超时，只得了40分。 
    //rem[u][x][y]表示：我们是否通过第二天第u家店的菜价和第一天第u-1家和第u家的菜价进行过DFS递归
    //如果进行过，就说明后面的DFS递归跟前面某次的DFS递归是重复的，最后势必得到同样的答案，就不用进行下去了。 
    bool rem[MAXN][MAXN][MAXN];   
    
    /*
    ** 参数： 
    ** u: 第二天的第u个店
    ** x: 第一天的第u-1个店的菜价
    ** y: 第一天的第u个店的菜价 
    **  
    ** 当前层DFS的功能： 
    ** 通过第二天第u个店的菜价 
    ** 和第一天第u-1个店的菜价x
    ** 和第一天第u个店的菜价y
    ** 来计算第一天第u+1个店的菜价 
    */ 
    void DFS(int u,int x,int y){
    	//进行剪枝，没有rem数组进行剪枝的话会超时，只得了40分。 
    	if(rem[u][x][y]){  
    		return ;
    	}
    	rem[u][x][y] = true;
    	if(u == n){
    		/*
    		**这个时候我们已经把第一天每个商家的菜价求出来了，
    		**但是需要用下面的两个if语句把第n家的菜价检查一下  
    		*/
    		int sum = b[n-1]*3 - a[n-2];
    		/*
    		** 这个外层if语句其实我不是很理解，一开始我是没有这一层判断的
    		** 我觉得我在前面求得时候就已经符合这个if条件的要求
    		** 但是不加的话结果就只有70分，加上之后就100分了。 
    		*/  
    		if( (sum/2)==b[n] || (sum+1)/2==b[n] || (sum+2)/2==b[n]){
    			//第一天第n-1家商店菜价（a[n-1]）和第n家商店菜价(a[n])的平均值为b[n] 
    			/*
    			** 这个if语句是因为：
    			** 我们在计算第一天第n家店的菜价(a[n])时，只通过a[n-1],a[n-2]和b[n-1]衡量过
    			** 但是并没有通过a[n-1]和b[n]衡量过。 
    			*/
    			if(a[n] + a[n-1]>=2*b[n] && a[n]+a[n-1]<=2*b[n]+1){   
    				replace();
    				return ;
    			}
    		}
    	}
    	for(int sum=b[u]*3;sum<=b[u]*3+2;sum++){
    		a[u+1] = sum - a[u] - a[u-1];
    		if(a[u+1] <= 0){
    			continue;
    		}
    		DFS(u+1,a[u],a[u+1]);		
    	}
    } 
    
    int main(){
    	cin>>n;
    	for(int i=1;i<=n;i++){
    		cin>>b[i];
    	}
    	for(int sum=b[1]*2;sum<=b[1]*2+1;sum++){
    		for(int x=1;x<sum;x++){
    			a[1] = x;
    			a[2] = sum - x;
    			DFS(2,a[1],a[2]);	
    		}
    	}
    	for(int i=1;i<n;i++){
    		cout<<ans[i]<<" ";
    	}
    	cout<<ans[n]<<endl;
    	return 0; 
    }

[20200302173152333.png]: https://img-blog.csdnimg.cn/20200302173152333.png