1. P1378 油滴扩展

题意

在长方形框中，最多有 n ($0\le{n}\le6$)个相异点，在框中点上依次放置可扩展的油滴，当碰到其他油滴边界或者长方形边框时会停止，扩展呈圆形展开。放置下一个时会确保上一个已经扩展完成。问通过变换放置顺序可使得最终框中剩下的面积最小为多少。

思路

这是个裸的dfs，情况最多也就 $6! = 720$ 种，所以我们可以只需要设置一个vis数组来记录是否已经放置过这个油滴，计算已扩展油滴和将要放的油滴之间的距离可以用 两点距离-扩展油滴的半径来实现 ，但是有个坑需要注意，就是当一个油滴已经放在已经有扩展油滴覆盖的区域，那么他俩的距离是0，而不是负数，因此在计算半径的时候需要优化一下。

代码实现

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>

#define pi 3.1415926
using namespace std;

const int maxn=10;
int n,x,y,xx,yy;
double rx[maxn];
double maxans;
bool vis[maxn];
int dx[maxn],dy[maxn];
double diss(int x1,int y1,int x2,int y2) //计算两点距离
{
	return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
double radius(int p) //计算半径
{
	double ans=min(abs(dx[p]-x),min(abs(dy[p]-y),min(abs(dx[p]-xx),abs(dy[p]-yy))));
	for(int i=1;i<=n;i++)
	{
		if(vis[i]&&i!=p)
		{
			double dis=diss(dx[i],dy[i],dx[p],dy[p]);
			ans=min(ans,max(dis-rx[i],0.0)); 
		}
	}
	return ans;
}
void dfs(int nowcnt,double area) //area为拓展总面积 nowcnt为现在已经放置了几个 
{
	if(nowcnt==n)
	{
		maxans=max(maxans,area);
		return ; 
	}
	for(int i=1;i<=n;i++)
	{
		if(!vis[i])
		{
			vis[i]=true;
			rx[i]=radius(i);
			dfs(nowcnt+1,area+pi*rx[i]*rx[i]);
			rx[i]=0;
			vis[i]=false;
		}
	}
}
int main()
{
	scanf("%d",&n);
	scanf("%d%d%d%d",&x,&y,&xx,&yy);
	double sum=abs(x-xx)*abs(y-yy); //矩形总面积 
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&dx[i],&dy[i]);
	}
	dfs(0,0.0);
	printf("%0.0lf",sum-maxans);
	return 0;
}

2. P1120 小木棍

题意

将一些长度为 x 的等长木棍全部切成 n 段不超过50的小木棍，求长木棍长度 x 的最小长度。

思路

首先这个题是有个坑的，题目给出来了，输入的小木棍长度可能会有大于50的，因此我们需要筛掉它。

那么很显然这个题是一道搜索题，我们可以写搜索函数dfs(int nowcnt,int nxt,int lenlast,int len).上述参数分别表示: 现在在寻找第几根小木棍，我们寻找下一个拼接段应该从哪里开始找，当前这根拼接还需要多长，以及我们要拼成多长的木棍。搜索的复杂度这么高，对于 $n\le65$ 的数据肯定不能直接无脑搜，因此需要想想怎么优化。

  • 首先要从大到小排序这个很关键的，因为你从大的先凑就能够保证后面选择的时候容错率更高一些。

  • 很显然我们可以剪掉当 lenlast<0 的情况，这个地方我们可以在拼接的时候就判断，也可以在拼接后判断。

  • 在寻找下一个拼接片段的时候，我们可以通过二分搜索来查找下一个不超过lenlast的片段，我选择了直接用STL的库中的lower_bound函数。(其实因为是我的二分总是写炸)

  • 再就是我们对于相等片段的处理，很显然当前片段不符合情况那么与他等长的也都不会符合，因此我们可以直接循环筛掉。当然更优的方法可以提前处理一个跳表，直接跳到下一个与他不同的位置。

  • 最后这个优化还是挺难想的，就是如果当前片段搜下去已经不符合情况，但是当前的lenlast是等于当前片段长度的，也就是说你正好用了尽可能满足条件的一个方案，也还是没达到目的，你们你继续往下搜，用比他还要劣的方案肯定也是不可能的，因此直接就break跳出循环不需要往下搜了。

    不过就算加了这么多优化我还是T了三个点，直接 O2一开跑路了嘿嘿

代码实现

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

const int maxn=70;
int n,a[maxn],temp,icnt=1;
int totlen,maxlen,cnt;
bool vis[maxn],finish;
int cmp(int a,int b)
{
	return a>b;
}
void dfs(int nowcnt,int nxt,int lenlast,int len)
//nowcnt:现在正在拼接第几根 
//nxt:我们应该从哪里开始检索 
//lenlast:现在拼接还需要多少才能拼接完成 
//len:每根木棍的理想长度 
{
	if(lenlast<0) return;
	if(lenlast==0)
	{
//		printf("test\n");
		if(nowcnt==cnt) 
		{
			printf("%d\n",len);
			finish=true;
			return ;
		}
		int p=1;
		for(p=1;p<=n;p++) if(!vis[p]) break;
		vis[p]=true;
		dfs(nowcnt+1,p+1,len-a[p],len);
		if(finish) return ;
		vis[p]=false;
	}
	else
	{
		int pos=lower_bound(a+nxt,a+1+n,lenlast,greater<int>())-a;
		for(int i=pos;i<=n;i++)
		{
//			printf("what\n");
			if(!vis[i]&&lenlast-a[i]>=0)
			{
				vis[i]=true;
				dfs(nowcnt,i+1,lenlast-a[i],len);
				if(finish) return;
				vis[i]=false;
				
				while(a[i+1]==a[i]) i++;
				if(i==n) return;
				if(lenlast-a[i]==0) break; 
			}
		}
	}
}
int main()
{
//	freopen("test.in","r",stdin);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&temp);
		if(temp>50) a[i]=0;
		else a[i]=temp;
		maxlen=max(maxlen,a[i]);
		totlen+=a[i];
	}
	sort(a+1,a+1+n,cmp);
	while(!a[n]) n--;
	for(int l=maxlen;l<=totlen;l++)
	{
		finish=false;
		if(totlen%l!=0) continue;
		cnt=totlen/l;
		vis[1]=true;
		dfs(1,2,l-a[1],l);
		vis[1]=false;
		if(finish) return 0;
	}
	return 0;
}

3. YOKOF - Power Calculus

题意

给出一个正整数 n ，只能使用乘法或者除法，可以乘除 $x$ 或者过程中产生的中间值 $x^i$ ，输出使得 $x$ 变为 $x^n$ 所需的最少步数。$(n\le100)$

思路

很显然我们一直是对指数进行操作，看似是乘除，直接转化为指数的加减。因此我们需要记录一个状态数组来记录乘除中间所产生的 $x^i$ ，以便后续过程中使用。但是这道题直接搜索的话，又会超时，因为他把大量的时间浪费在高深度上，但是这个却不一定是最优解。因此需要用到迭代加深搜索(IDDFS).

迭代加深搜索(IDDFS)主要用于处理一些题目可能会搜到很深但是答案却不是最优的问题。有的时候dfs搜索的深度是无穷的，而且他的复杂度是呈指数级增长的，因此这其中某些情况就可以用IDDFS，在每次搜索的时候，我们给深度一个限制，当达到这个最大深度却没有得到答案的时候，就返回，然后逐步提升深度，这样我们就可以避免将时间浪费在那些无谓的高深度搜索上了。

$$ \sum_{i=0}^n2^i=2^{n+1}-1（指数级别增长实例） $$

代码实现

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>

using namespace std;
int n;
int x[1005]; //用来记录每次生成的中间状态 
bool dfs(int k,int dep,int maxdep)
{
	if(k<=0||dep>maxdep||k<<(maxdep-dep)<n) return false;
	if(k==n||k<<(maxdep-dep)==n) return true;
	x[dep]=k;
	for(int i=0;i<=dep;i++)
	{
		if(dfs(k+x[i],dep+1,maxdep)) return true; //对应乘法 
		if(dfs(k-x[i],dep+1,maxdep)) return true; //对应除法 
	}
	x[dep]=0;
	return false;  
}
int main()
{
	while(scanf("%d",&n)&&n)
	{
		for(int i=0;;i++)
		{
			if(dfs(1,0,i))
			{
				printf("%d\n",i);
				break;
			}
		}
	}
}