轮廓线DP：poj 2279 Mr. Young's Picture Permutations

poj 2279 Mr. Young's Picture Permutations

$ solution: $

首先摘取一些关键词：（每行不超过它后面的行）（每排学生安排高度从左到右减少）（学生的高度应该从后面到前面减少）。这个已经很提示我们轮廓线DP了。而且这一题的数据范围也十分的小：行数不超过五行，人数不多于三十人。这么小的数据范围基本上可以断定是DP了。

然后这种带限制条件的我们可以想办法满足，比如说身高问题我们一般都会采取填人的办法（这一题按身高从大到小填（当然反过来也可以）），然后我们就可以将这个身高问题转换成如果前面的那一行比我们要填的这一行要长那么我们这一行就不能填，然后直接将符合条件的情况转移即可。（详细见代码）

$ code: $

#include<iostream>
#include<cstdio>
#include<iomanip>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>

#define ll long long
#define db double
#define inf 0x7fffffff
#define rg register int

using namespace std;

int n;
int a[7];
ll f[31][17][11][9][7];

inline int qr(){
	register char ch; register bool sign=0; rg res=0;
	while(!isdigit(ch=getchar())) if(ch=='-')sign=1;
	while(isdigit(ch)) res=res*10+(ch^48),ch=getchar();
	return sign?-res:res;
}

int main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	while(n=qr()){
		for(rg i=1;i<=5;++i) a[i]=0;
		for(rg i=1;i<=n;++i) a[i]=qr();
		for(rg i=0;i<=a[1];++i)
			for(rg j=0;j<=a[2];++j)
				for(rg p=0;p<=a[3];++p)
					for(rg q=0;q<=a[4];++q)
						for(rg k=0;k<=a[5];++k)
							f[i][j][p][q][k]=0;
		f[0][0][0][0][0]=1;
		for(rg i=0;i<=a[1];++i)
			for(rg j=0;j<=a[2];++j)
				for(rg p=0;p<=a[3];++p)
					for(rg q=0;q<=a[4];++q)
						for(rg k=0;k<=a[5];++k){
							if(!f[i][j][p][q][k])continue;
							if(k<a[5])f[i][j][p][q][k+1]+=f[i][j][p][q][k];
							if(q<k&&q<a[4])continue;
							if(q<a[4])f[i][j][p][q+1][k]+=f[i][j][p][q][k];
							if(p<q&&p<a[3])continue;
							if(p<a[3])f[i][j][p+1][q][k]+=f[i][j][p][q][k];
							if(j<p&&j<a[2])continue;
							if(j<a[2])f[i][j+1][p][q][k]+=f[i][j][p][q][k];
							if(i<j&&i<a[1])continue;
							if(i<a[1])f[i+1][j][p][q][k]+=f[i][j][p][q][k];
						}
		printf("%lld
",f[a[1]][a[2]][a[3]][a[4]][a[5]]);
	}
	return 0;
}