POJ1037-A decorative fence-DP，求字典序第i个序列

参考：

一、求字典序的第i个排列

参见：  http://jay23jack.blog.163.com/blog/static/317951942009130215813/

 

      暴力枚举可以很轻松地得到符合的排列，事实上不妨ms写一个，来产生更强的样例。当然，答案不会是暴力，而是一种很常见的方法，可以说是这种求指定编号问题的通法吧！
      直接一位一位枚举答案！从前到后枚举求得每一位：枚举一位时，计算在这样的前缀下，后面的总的排列数。如果严格小于总编号，则该位偏小，换更大的数，同时更新总编号；若大于等于，则该位恰好，枚举下一位，总编号不用更新。
      先抛开此题，用最简单的全排列问题来说明这种方法。如1，2，3，4的全排列，共有4！种，求第10个的排列是？
      先试首位是1，后234有3！=6种<10,说明1偏小，转化成以2开头的第（10-6=4）个排列，而3！=6 >= 4，说明首位恰是2。
      第二位先试1（1没用过），后面2！=2个<4,1偏小，换成3（2用过了）为第二位，总编号也再减去2！，剩下2了。而此时2!>=2，说明第二位恰好是3。
      第三位先试1，但后面1！<2，因此改用4。末位则是1了。
      这样得出，第10个排列是2-3-4-1。（从1计起）
      这种方法的核心在于求，给定前缀下后面总的排列数。全排列问题较易求。同时还需记录前面用过的数字。
      再回到此题，同是这样来求。但求后面总的排列数时，用到了递推，或者说dp，不难的方程。
      搞懂了后，去poj上做题，先是WA，试过书上的样例后，发现忘记判断“波浪形”了。于是慨叹，强大的数据是成功调试的有力保证！以后还是要不厌其烦地写一些样例来才行啊！

 

Sam：在求字典序的第i个排列时，关键是求得每种特定前缀子串的可能排列数目，如上面例子中，要求出字典序第i大，需要知道以下序列的个数 (*代表可以使任何可能数字)：

          1 * * *

                    1 2 * *

                              1 2 3 *

                              1 2 4 *

                    1 3 * *

                              1 3 2 *

                              1 3 4 *

                    1 4 * *

                              1 4 2 *

                              1 4 3 *

          2 * * *

                    2 1 * *

                              2 1 3 *

                              2 1 4 *

                    2 3 * *

                              2 3 1 *

                              2 3 4 *

                    2 4 * *

                              2 4 1 *

                              2 4 3 *

 

二、DP

 

参见： http://hi.baidu.com/superlong/blog/item/783eb18f9aa063e7f11f36ba.html

      这个题目的意思很纠结，是给你一个序列的长度，然后给你一个排列规则，让你输出字典序第m的排列。这个排列规则是这样的：对于排列中的每一个数都有：(a[i]>a[i-1] && a[i]>a[i+1]) || (a[i]<a[i-1] && a[i]<a[i+1])，这个题是用dp加上所谓数学方法（黑书p257），不过另外的dp方程也是可以的，即 DP.down[i][l] 表示以i开始，长度为l，并且初始初始状态是向下放置的（即第二个数小于第一个数），同样DP.up[i][l]就不解释了，那么就有
      DP.down[i][l] =  sigema{DP.up[[k][l-1](1<=k<i)}
      DP.up[i][l]     =  sigema{DP.down[l+1-i][l].
      这样我们可以得到任意状态的排列数，然后就是麻烦的输出了。

-------------------------------------------------------------------------------------------------------------------------------------

 

代码：

//poj 1037 A decorative fence 经典的DP+计数
#include <iostream>
using namespace std;
int n;
__int64 m;
__int64 dp[21][21][2];
int mark[21];//mark[i]=1表示长度为i的plank已经使用
int main()
{
	//1. DP
	dp[1][1][0]=dp[1][1][1]=1;
	for (int len=2;len<=20;len++){
		for (int i=1;i<=len;i++)
		{
			for (int j=1;j<i;j++) dp[len][i][0]+=dp[len-1][j][1];
			for (int j=i;j<len;j++) dp[len][i][1]+=dp[len-1][j][0];//?为什么这里不是n呢???
		}
	}

	//2. 求字典序第i个排列
	int t;
	scanf("%d",&t);
	while (t--)
	{
		scanf("%d%I64d",&n,&m);
		int l=1,r=n,j,finded=0;
		memset(mark,0,sizeof(mark));
		for (int i=1;i<=n && !finded;i++)
		{
			for (j=0;j<2;j++)
			{
				m-=dp[n][i][j];
				if (m<=0) {
					m+=dp[n][i][j];		//第n位是i，跳出这两个for后需要寻找前缀是1的字典序第m个序列
					mark[i]=1;
					printf("%d",i);
					if (j==0) l=1,r=i-1;
					else l=i+1,r=n;

					finded=1;

					break;
				}
			}
		}

		j^=1;
		for (int len=n-1;len>=1;len--)	//依次找到第(n-1)~1位
		{
			int num=0;
			for (int i=1;i<l;i++) if (!mark[i]) ++num;//本位置剩余可以尝试的数字个数: num???

			for (int i=l;i<=r;i++)
				if (!mark[i])
				{
					num++;
					m-=dp[len][num][j];
					if (m<=0){
						m+=dp[len][num][j];
						mark[i]=1;
						printf(" %d",i);
						if (j==0) l=1,r=i-1;
						else l=i+1,r=n;
						j^=1;
						break;
					}
				}
		}
		printf("\n");

	}
	system("pause");
	return 0;

}