前言：所有递归都可以转化为递归搜索树！

AcWing 92

深度优先搜索的递归实现指数型枚举，画颗树分析吧。

#include<bits/stdc++.h>

using namespace std;

const int N = 15;

int n;//有几个数字 
int st[N];//记录每个位置当前的状态：0为未处理，1为选中，2为不选 

void dfs(int u)//u为为数组下标，u+1为第几个数 
{
	if(u == n)//说明所有数已经选择完毕 
	{
		for(int i=0;i<n;i++)
		{
			if(st[i]==1)
			{
				printf("%d",i+1); 
				printf(" "); 
			}
		}
		printf("\n");
		return;
	}
	
	st[u]=2;//第一分支：不选 
	dfs(u+1);//递归 
	st[u]=0;//该行代码在此题中有无都不影响，但在其他题中可能产生影响 
	
	st[u]=1;//第二分支：选中 
	dfs(u+1);//递归 
	st[u]=0;//同上 
} 
          
int main()
{

	cin >> n;
	
	dfs(0);//数组下标从0开始，0为第一个数 
	
	return 0; 
}

AcWing 102

利用绝对值不等式找到距离的数量关系，得出中位数货仓离其他货仓距离之和最小。

#include<bits/stdc++.h>

int main()
{
	int n;
	scanf("%d",&n);
	int a[n+1];
	
	for(int i=0;i<n;i++)
		scanf("%d",&a[i]);
	
	sort(a,a+n);
	
	long long sum=0;
	int flag=a[n/2];
	
	for(int i=0;i<n;i++)
		sum+=abs(a[i]-a[n/2]);
	
	printf("%lld",sum);
	
	return 0;
} 

AcWing 1055

易知：第1天买，第n天卖，等同于第1天买，第2天卖了又买，第3天卖了又买，以此类推一直到第n天卖。故理论上只要有某一天价格低于后一天，就可以赚这个差价，即调整这两天的买卖策略变为前一天买了不卖，后一天卖了不买，直到下一次遇见同样的情况再重复同样的操作。

也就是说，所有后一天高于前一天的差价都可以赚到，故只要把这些差价都加起来就是最大利润（卖股票就是赚差价，不会有更大的了）

#include<bits/stdc++.h>

const int N=100010;
int n,price[N];

int main(){
	int sum=0;
	scanf("%d",&n);
	
	for(int i=0;i<n;i++)
	    scanf("%d",&price[i]);
	
	for(int i=0;i<n-1;i++)
	{
		if(price[i+1]>price[i])
		{
			sum+=price[i+1]-price[i];
		}
	}
	
	printf("%d",sum);
	
	return 0;
}

AcWing 112

列式子，推导表达式

#include<bits/stdc++.h>

typedef long long LL; 
const int N = 1000010; 

int n;
int a[N];
LL c[N];

int main()
{
	scanf("%d",&n);
	
	LL sum=0;
	
	for(int i = 1; i <= n; i++)
	{
		scanf("%d", &a[i]);	
		sum+=a[i];
	}
		
	long long ave = sum / n;
	
	for (int i = n; i > 1; i--)
	{
		c[i] = c[i + 1] + ave - a[i];
	}
	c[1] = 0;
	
	sort(c + 1,c + n + 1);
	
	long long res = 0;
	for(int i =1; i <= n; i++)
		res += abs(c[i] - c[(i + 1) / 2]);
	
	printf("%lld\n", res);	
	
	return 0;
}