TopCoder SRM 590 Div2 第3題

類型：dp 難度：2.5

題目大意：一張圖有多列，每列有'U'，'D'，'.'的排列。U表示可向上走，D表示可向下走，.表示為空，U和P不能交叉或重合，問有幾種擺法

例如：

".D."

"..."

".U."

有三種擺法，分别為：

".D."

"..."

".U."

"..."

".D."

".U."

".D."

".U."

"..."

分析：整體思路是，算出每一列的擺法，然後依次相乘，即為結果。

而對于計算每一列的擺法，做的時候走了很多彎路，一開始有遞歸+枚舉的辦法，每一列從上往下依次周遊，對于U和D分别處理，因為U從上往下周遊即可遞歸計算，而D需從下往上遞歸計算，故看成一段U一段D的分割，分别計算。但是由于遞歸複雜度很高，最後逾時。

後來一直想不明白，講一個子問題請教了了大神~發現是動态規劃的問題，關于子問題“序列中隻含有U或D”的解法參見大神部落格http://blog.csdn.net/vinson0526/article/details/11562767

最終關于此題的完整解法如下：

對于每一列，先記錄每個U或P的出現位置

dp[i][j]記錄第i個U或P在第j行可能出現的次數。

則遞推公式為：dp[i][j] = sum(dp[i-1][k]) , 0<=k<j

即：第i個U或P在第j行可能出現的次數為第i-1個U或P在之前所有位置[0,j)可能出現次數的和

之後，若為U，則j從U出現位置向上周遊；若為D，j從D出現位置向下周遊

最外層循環再依次周遊每個U或P即可。

最後注意初始化，将第1個U或P從出現位置向上/下全部置為1

代碼如下：

#include<string>
#include<vector>
#include<cstring>
#include<map>
#include<iostream>
#include<algorithm>
using namespace std;

#define MAX(x,y) (x)>(y)?(x):(y)

const int mol = 1000000007;
const int MAX = 55;

class FoxAndShogi
{
	public:		
		int row,col;
		map<string,int> rec;
		
		int cal(string col)
		{			
			int pos[MAX][2];
			memset(pos,0,sizeof(pos));
			
			int cnt = 0;
			int n = col.length();
			
			
			for(int i=0; i<n; i++)
			{
				if(col[i]=='U') 
				{
					pos[cnt][0] = i;
					pos[cnt++][1] = -1;
				}
				else if(col[i]=='D')
				{
					pos[cnt][0] = i;
					pos[cnt++][1] = 1;
				}
			}
			
			if(cnt==0) return 1;
			
			int dp[MAX][MAX];
			memset(dp,0,sizeof(dp));
			
			for(int i=pos[0][0]; i>=0 && i<n; i+=pos[0][1])
				dp[0][i] = 1;
			
			
			for(int i=1; i<cnt; i++)
			{
				for(int j=pos[i][0]; j>=0 && j<n; j+=pos[i][1])
					for(int k=0; k<j; k++)
					{
						dp[i][j] += dp[i-1][k];
						dp[i][j] %= mol;
					}
			}
			/*
			for(int i=0; i<cnt; i++)
			{
				for(int j=0; j<n; j++)
					cout<<dp[i][j]<<" ";
				cout<<endl;
			}*/
			int ans = 0;
			for(int i=0; i<n; i++)
			{
				ans += dp[cnt-1][i];
				ans %= mol;
			}
			return ans % mol;
		} 
		
		int differentOutcomes(vector <string> board)
		{
			long long ans = 1;
			
			row = board.size();
			col = board[0].length();
			
			for(int j=0; j<col; j++)
			{
				string coltmp;
				coltmp.resize(row);
				for(int i=0; i<row; i++)
				{
					coltmp[i] = board[i][j];
				}
				
				int cnt;
				if(rec[coltmp]>0) 
					cnt = rec[coltmp];
				else 
				{
					cnt = cal(coltmp);
					rec[coltmp] = cnt;
				}
				
				ans = (ans * cnt) % mol;
			}
			
			return ans % mol;
		}	
};