POJ 1739 - Tony's Tour

http://poj.org/problem?id=1739

A square township has been divided up into n*m(n rows and m columns) square plots (1<=N,M<=8),some of them are blocked, others are unblocked. The Farm is located in the lower left plot and the Market is located in the lower right plot. Tony takes her tour of the township going from Farm to Market by walking through every unblocked plot exactly once.
Write a program that will count how many unique tours Betsy can take in going from Farm to Market. 

Input

The input contains several test cases. The first line of each test case contain two integer numbers n,m, denoting the number of rows and columns of the farm. The following n lines each contains m characters, describe the farm. A '#' means a blocked square, a '.' means a unblocked square.
The last test case is followed by two zeros. 

Output

For each test case output the answer on a single line.

Sample Input

2 2
..
..
2 3
#..
...
3 4
....
....
....
0 0

Sample Output

1
1
4

https://blog.csdn.net/Mitsuha_/article/details/77506071

这是第一次写这样的插头DP，状态转移有点复杂。主要参考了http://blog.csdn.net/xingyeyongheng/article/details/24415517

不过还没了解什么是插头DP的话，建议先仔细认真的看陈丹琦的《基于连通性状态压缩的动态规划问题》https://wenku.baidu.com/view/a6dce6c76137ee06eff918d1.html

https://www.cnblogs.com/newera/p/9141667.html

这题除了一开始的预处理，基本上就是插头dp$dp$的模板题了

由于插头dp$dp$求的是Hamilton$Hamilton$回路，而此题有起点和终点的限制

于是可以构造一条[n,1]−>[n+2,1]−>[n+2,m]−>[n,m]$[n,1]->[n+2,1]->[n+2,m]->[n,m]$的路径，正好只添加一条S−>T$S->T$的路径

接下来就是插头dp$dp$的模板了

推荐三篇文章，看完基本上就懂插头dp$dp$了吧，

litble：https://blog.csdn.net/litble/article/details/79369147

yhzq：远航之曲博客

陈丹琦论文：http://www.doc88.com/p-9009338580746.html

可以发现，插头dp$dp$其实就是对于当前已枚举部分和未枚举部分的轮廓线的状压dp$dp$

注意每枚举过一行要将所有状态左移一位（下一行会多出来一个状态位）

http://www.cnblogs.com/kuangbin/archive/2012/09/30/2709114.html

插头DP。题目意思就是从左下角走到右下角，每个非障碍格子都走一遍的方法数。

一种方法是后面加两行转化成回路问题。

转成回路问题就和这题一样了：http://www.cnblogs.com/kuangbin/archive/2012/09/29/2708989.html

 

也可以不增加行，只要在起点和终点特殊处理下即可。

http://www.acmsearch.com/article/show/17209
这题很容易想到把左下和右下两个格子连起来，构成一条哈密顿回路，就和上一题一样，不过这条路有一条必须经过的路径，我们需要特殊处理，做法有两种，我是添加了一层，然后特殊处理最后一层，后来发现小hh的解法说不用，又写了另一种解法，就是将最后一层的状态变成初始状态，然后从底往上dp，这种写法比较好，简单，而且状态比第一种写法少。

POJ 1738 - An old Stone Game

http://poj.org/problem?id=1738

There is an old stone game.At the beginning of the game the player picks n(1<=n<=50000) piles of stones in a line. The goal is to merge the stones in one pile observing the following rules:
At each step of the game,the player can merge two adjoining piles to a new pile.The score is the number of stones in the new pile.
You are to write a program to determine the minimum of the total score. 

Input

The input contains several test cases. The first line of each test case contains an integer n, denoting the number of piles. The following n integers describe the number of stones in each pile at the beginning of the game.
The last test case is followed by one zero. 

Output

For each test case output the answer on a single line.You may assume the answer will not exceed 1000000000.

Sample Input

1
100
3
3 4 3
4
1 1 1 1
0

Sample Output

0
17
8

https://www.fengiling.com/blog/view/?id=711857

有n堆石头排成一条直线 ，每堆石头的个数已知，现在要将这n堆石头合并成一堆，每次合并只能合并相邻的两堆石头，代价就是新合成石头堆的石头数，现在问将这n堆石头合并成一堆，最小代价是多少？

如果n的值较小，那么可以用dp[i][j]表示i-j堆合并成一堆的最小代价，那么dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[i][j])

用区间DP做的代码

    while(scanf("%d",&n)!=EOF)
    {
        if(n==0)
            break;
        for(int i=1; i<=n; i++)
            for(int j=i; j<=n; j++)
                dp[i][j]=INF;
        sum[0]=0;
        for(int i=1; i<=n; i++)
        {
            scanf("%d",&a[i]);
            sum[i]=sum[i-1]+a[i];
            dp[i][i]=0;
        }

        if(n==1)
            printf("0
");
        else
        {
            for(int d=2; d<=n; d++)
            {
                for(int i=1; i<=n; i++)
                {
                    int s=i;
                    int e=i+d-1;
                    int add=sum[e]-sum[s-1];
                    for(int k=s; k<=e; k++)
                    {
                        dp[s][e]=min(dp[s][e],dp[s][k]+dp[k+1][e]+add);
                    }
                }
            }
            printf("%d
",dp[1][n]);
        }
    }

但是数据非常大，需要用GarsiaWachs算法，参考http://barty.ws/poj-1738-%E7%9F%B3%E5%AD%90%E5%90%88%E5%B9%B6%E7%9A%84garsiawachs%E7%AE%97%E6%B3%95/

石子合并问题的普遍做法是动态规划。dp[i][j]表示从i合并到j这段石子所需的最小代价和。从小到大枚举区间就行了，此时复杂度为O(N^3)。又因为有四边形不等式优化，设f[i][j]为区间[i,j]的最优分界点，则有f[i][j-1]<=f[i][j]<=f[i+1][j]，复杂度就降为O(N^2)。

此时对于N=50000的复杂度来说依然不可接受。Knuth在TAOCP里有一个很神奇的算法，叫做GarsiaWachs。具体算法如下：

step 0：初始数组为num[1..n]，num[0] = num[n+1] = INF

step 1：每次找到一个最小的i使得num[i-1]<=num[i+1]，将num[i-1]和num[i]合并为temp

step 2：找到前面一个最大的j使得num[j]>temp，将temp放在j之后。

step 3：重复1,2，直到剩余的堆数为1。

因为每次step2之后，指向的位置只需要向前一个即可(前面其他的都不会受到此次更新的影响)，因此每次指针的移动并不多。也因此，一个理论复杂度其实有O(N^2)的算法能够轻松过掉这道题。

https://www.cnblogs.com/lightspeedsmallson/p/4899584.html

还是石子归并问题，但是因为现在石子有50000堆，就需要开int[50000][50000]的数组，无论空间还是时间都可能挂掉，就得寻求更好的方法。

GarsiaWachs算法是从第一个石堆开始找符合stone[k-1]<stone[k+1]的石堆k，然后合并k-1与k堆，再向前找j堆石子，满足stone[j]>stone[k]+stone[k-1],插入到石堆j的后面。然后重新寻找。

我觉得GarsiaWachs算法的想法就是把石子就想象成是三堆，k-1 k k+1堆，如果stone[k-1]<stone[k+1]，那么一定是先合并k-1与k堆是合理的，之后把合并的堆插入到stone[j]的后面，是把stone[j+1]与stone[k-2]看成一个整体stone[m],所以现在就是stone[j],stone[m],(stone[k-1]+stone[k])，因为stone[k-1]+stone[k]<stone[j],所以插入到stone[j]后面是希望(stone[k-1]+stone[k])与stone[m]先合并，这样就不断地都是最优解，得到的结果也就是最优结果。

http://www.aichengxu.com/suanfa/10961063.htm

石子合并问题升级版（因为n<=5W）
不得不先吐槽一下，我只是搜了一下POJ简单石子合并问题，然后就开心的去写1738了，然后感觉n好大呀，结果一看Source男人八题，QAQ，度娘太坑人了QAQing
分析：
因为n<=5W，开个dp数组根本开不下，所以我们要学习一种萌萌哒的算法——GarsiaWachs算法
我们先从最简单的看起，n=3时：
ans1=（a+b）+（（a+b）+c）
ans2=（b+c）+（（b+c）+a）
假设ans1<=ans2，==>a<=c
GarsiaWachs算法便是基于这种性质，每一次都在当前石子中找到最小的num[i-1]<=num[i+1]，然后将num[i-1]和num[i]合并为sum，然后从右往左找第一个num[j]大于等于sum的j，把sum插入到j的后面…………有个问题？？这样做不会违背只能合并相邻石子的性质吗？？Of course不会我们可以num[j+1]~num[i-2]看做一个num[mid]的整体，因为num[j]>=num[i-1]+num[i]所以我们一定是先合并sum，所以把sum放在num[mid]前面还是后面都没有关系啦
by >o< neighthorn

https://www.fengiling.com/blog/view/?id=711857

POJ 1737 - Connected Graph

http://poj.org/problem?id=1737

An undirected graph is a set V of vertices and a set of E∈{V*V} edges.An undirected graph is connected if and only if for every pair (u,v) of vertices,u is reachable from v.
You are to write a program that tries to calculate the number of different connected undirected graph with n vertices.
For example, there are 4 different connected undirected graphs with 3 vertices.

Input

The input contains several test cases. Each test case contains an integer n, denoting the number of vertices. You may assume that 1<=n<=50. The last test case is followed by one zero.

Output

For each test case output the answer on a single line.

Sample Input

1
2
3
4
0

Sample Output

1
1
4
38

https://oi.men.ci/poj-1737/

给定 $N$（$N \leq 50$）个点，在平面上固定其位置，求这些点最多能组成多少个不同的无向连通图。

统计连通图的方案数是困难的，但我们可以轻易地计算出用 N 个点组成任意图的方案数：因为 N 个点的无向图最多有 $\frac{N(N - 1)}{2}$ 条边，考虑每条边选或不选，则共有 $2 ^ {\frac{N(N - 1)}{2}}$种不同的图。

求出任意图的方案数后，只要再求出非连通图的方案数，就可以得到答案。考虑 $N$ 个点组成的非连通图中的点 $v$，它一定处于一个由 $K$（$1 \leq K \leq N - 1$）个点组成的连通分量中，点 $v$ 确定后，组成这个连通分量还需要 $K - 1$ 个点，总方案数为 $\binom{N - 1}{K - 1}$；每个连通分量都是一个连通图，可以递归来求；考虑完一个连通分量，图的剩余部分（与该连通分量隔离的 $N - K$ 个点）是一个任意图，也可以递归来求。

设 $n$ 个点组成连通图的方案数为 $f(n)$、组成非连通图的方案数为 $g(n)$、组成任意图的方案数为 $h(n)$，则递归计算 $f(n)$ 的公式为：

需要使用高精度。

http://www.voidcn.com/article/p-txqbeblo-bkm.html

    public static final int N = 55;
    public static void main(String[] args) throws Exception
    {
        BigInteger []h = new BigInteger[N];
        BigInteger []f = new BigInteger[N];
        BigInteger []g = new BigInteger[N];
        BigInteger p2[] = new BigInteger[N*N];
        BigInteger [][]C = new BigInteger[N][N];
        for (int i=0;i<N;i++)
        {
            for (int j=0;j<=i;j++)
            {
                if (i==j || j==0) C[i][j] = valueOf(1);
                else C[i][j] = C[i-1][j-1].add(C[i-1][j]);
            }
        }
        p2[0] = ONE;
        for (int i=1;i<N*N;i++)
            p2[i] = p2[i-1].multiply(valueOf(2));
        for (int i=0;i<N;i++)
            h[i] = p2[i*(i-1)/2];
        f[1] = BigInteger.valueOf(1);
        g[1] = BigInteger.valueOf(0);
        for (int n=2;n<N;n++)
        {
            g[n] = BigInteger.ZERO;
            for (int k = 1;k < n; k++)
            {
                BigInteger t = C[n-1][k-1].multiply(f[k]);
                t = t.multiply(h[n-k]);
                g[n] = g[n].add(t);
                f[n] = h[n].subtract(g[n]);
            }
        }
        Scanner in = new Scanner(System.in);
        while (in.hasNext())
        {
            int n = in.nextInt();
            if (n == 0) break;
            System.out.println(f[n]);
        }
    }

http://www.voidcn.com/article/p-zvbflxxn-uv.html

将总的方案数减掉所有不连通的方案。
总的方案数是2^(C(n,2))，不连通的方案数可以如下考虑：
当和点1连通的点数共有k个时，方案数为C(n-1,k) * F(k+1)，其他n-k-1各点间任意连边即可，方案数为2^(C(n-k-1,2))，所以这样的方案数共有C(n-1,k)* F(k+1)* 2^(C(n-k-1,2))种。
因此可以得到递推公式：
F(n)= 2^(C(n,2))-Sum(C(n-1,k)* F(k+1)* 2^(C(n-k-1,2)) | 0<=k < n)

https://blog.csdn.net/PoPoQQQ/article/details/43525019

令f[i]表示i个点能组成多少种无向图

首先易知我们能生成2^(i*(i-1)/2)种图 但是一些是不合法的 我们要将不合法的干掉

枚举1号节点与多少个点连通

设1号节点所在联通块大小为j(1<=j<=i-1)

那么与1相连的其它点有C(i-1,j-1)中选法，1号节点所在联通块有f[j]种连法，不与1号节点相连的点有2^((i-j)*(i-j-1)/2)种连法

故得到递推式f[i]=2^(i*(i-1)/2)-Σ[1<=j<=i-1]C(i-1,j-1)*f[j]*2^((i-j)*(i-j-1)/2)

w = open("out.out", "w")

 

f = [0] * 60

C = [[0] * 60 for i in range(60)]

 

for i in range(0,51):

C[i][0] = 1

for j in range(1,i+1):

C[i][j] = C[i-1][j] + C[i-1][j-1]

for i in range(1,51):

f[i] = 2**(i*(i-1)//2)

for j in range(1,i):

f[i] -= C[i-1][j-1] * (2**((i-j)*(i-j-1)/2)) * f[j]

w.write("\"%d\",\n" %f[i] )