POJ 3347 Kadj Squares

题意：

题目链接

思路：

最开始没思路不知道怎么判断
后来看了题解。。。
果然数据小(n<=50,len<=30)就可以随便瞎搞
开始时困扰我的是怎么求新加入的正方形的位置
原来是枚举已加入的每一个正方形，计算出紧挨当前正方形的位置，然后取max就可以了
至于正方形是否看得见
两两枚举判断（见代码）

code：（这道题其实看代码超级好理解）

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=60;
int n,l[N],r[N],len[N];
inline int read()
{
	int s=0,w=1; char ch=getchar();
	for(;'0'>ch||ch>'9';ch=getchar())if(ch=='-')w=-1;
	for(;'0'<=ch&&ch<='9';ch=getchar())s=(s<<1)+(s<<3)+(ch^48);
	return s*w;
}
int main()
{
	while(1)
	{
		n=read();
		if(!n) break;
		for(int i=1;i<=n;++i)
		{
			len[i]=read();l[i]=0;
			for(int j=1;j<i;++j)
				l[i]=max(l[i],r[j]-abs(len[i]-len[j]));
			r[i]=l[i]+2*len[i];
		}
		bool pd=0;
		for(int i=1;i<=n;++i)
		{
			for(int j=1;j<i;++j)
				if(len[j]>len[i]&&l[i]<r[j])l[i]=r[j];//左大右小
			for(int j=i+1;j<=n;++j)
				if(len[j]>len[i]&&r[i]>l[j])r[i]=l[j];//左小右大
			if(l[i]<r[i]) printf("%d ",i);
		}
		puts("");
	}
	return 0;
}