timus 1172. Ship Routes URAL 解题报告 组合DP

timus   1172. Ship Routes   URAL 解题报告

题目大意：有三个岛，每个岛上有n个城市，一个游客想要游览遍三个岛上的所有城市，最后再回到出发点…… 而且不能走陆路，因为陆路上有食人族，水路的话只有不同岛上的城市才有…… 求所有的可能的路径……       注意：如果一条路正好是回文串，那么只算一条！ 因为游客已经到达一个城市了，这个城市可能在某个岛上，是该岛上的一个城市，你不知道是那个城市，但有一点你必须清楚，那就是这个城市已经确定了，你不能说他有n*3种可能了，他只有一种可能，即便你不知道他到底是哪个城市…… 还有就是加入你从起点开始走，到达第二个岛的第一个城市或第二个城市，这两个不能算作一条相同的路……    这是常识，虽然我没读明白题目大意！

弄懂了上面的着一些再来看看题，当时没看懂，找到了UPC鱼神的代码恍然大悟。他是假设，姑且这么认为吧，游客到的是第一个到上的第一个城市，那么每个岛有n个城市，就相当于每个岛只能到达过n次，最后又回到1岛，其实回不回来都一个样，因为这不影响我们做题，只要第一次地点的城市也算上的话，那么最后把每个岛n次机会都用完正好停留在2岛或者3岛就好了，因为会起点的路径是确定的，对数目不会有影响！  又因为不能有类似于回文串之类的路径，所有我们只能除以2，回文串是城市回文串不是岛屿回文串……  那样的话不符合正常人理解范围，虽然我从题目中没有读到这样的描述……

参考代码： http://hi.baidu.com/longmenwaideyu/item/98235cd465a6ed3548e1ddb2

用c++实现，其中高精度没有给出代码，帮助理解还是不错的！

下面这份是 python ，说是做大数毫无压力 http://blog.csdn.net/utoppia/article/details/8956169

自己会实现的代码：java版本： dp[i][j][k][a]表示三个岛到达过的城市数量为分别为：i ,  j,  k。   a表示目前在哪个岛上。

状态转移的要求是，不能自己到自己岛上的城市，超过n次的话不用管，因为代码是从0往上DP的，顶多越界一下而已…… 初始化和组合之间的乘加关系自己慢慢体会吧

import java.io.*;
import java.math.BigInteger;
import java.util.*;

public class Main4 {
   
	static int N=33;
	static BigInteger big1=BigInteger.ONE;
	static BigInteger big0=BigInteger.ZERO;
	static BigInteger big2=BigInteger.valueOf(2);
    static BigInteger dp[][][][]=new BigInteger[N][N][N][3];
    static int n,k;
    public static void main(String[] args) throws IOException  {
        Scanner sc = new Scanner(System.in);
         
        
        	
        	 n = sc.nextInt(); 
        	 init(n);
        	 System.out.println((dp[n][n][n][1].add(dp[n][n][n][2])).divide(big2));
         
    }
   static void init(int  n){
	   
	   for(int i=0;i<=32;++i){
		   for(int j=0;j<=32;++j){
			   for(int k=0;k<=32;++k){
				   for(int t=0;t<3;++t){
					   dp[i][j][k][t]=big0;
				   }
			   }
		   }
	   }
	   dp[1][0][0][0]=big1;
	   for(int i=1;i<=n;++i){
		   for(int j=0;j<=n;++j){
			   for(int k=0;k<=n;++k){
				   for(int t=0;t<3;++t){
					  if(t==0){
						  dp[i][j+1][k][1]= dp[i][j+1][k][1].add(  dp[i][j][k][t].multiply(BigInteger.valueOf(n-j)) );
						  dp[i][j][k+1][2]= dp[i][j][k+1][2].add(  dp[i][j][k][t].multiply(BigInteger.valueOf(n-k)) );
					  }else if(t==1){
						  dp[i+1][j][k][0]= dp[i+1][j][k][0].add(  dp[i][j][k][t].multiply(BigInteger.valueOf(n-i)) );
						  dp[i][j][k+1][2]= dp[i][j][k+1][2].add(  dp[i][j][k][t].multiply(BigInteger.valueOf(n-k)) );
					  }else if(t==2){
						  dp[i+1][j][k][0]= dp[i+1][j][k][0].add(  dp[i][j][k][t].multiply(BigInteger.valueOf(n-i)) );
						  dp[i][j+1][k][1]= dp[i][j+1][k][1].add(  dp[i][j][k][t].multiply(BigInteger.valueOf(n-j)) );
					  }
				   }
			   }
		   }
	   }
	   
	   
   }
}
           

timus   1172. Ship Routes   URAL 解题报告