程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> hdu 5151 Sit sit sit(DP)

hdu 5151 Sit sit sit(DP)

編輯:關於C++

題目鏈接:hdu 5151 Sit sit sit

區間dp,dp[i][j]表示從i到j的方案數,每次枚舉i~j之間放最大值的位置,左右顏色不同的位置不能放最大值。

#include 
#include 
#include 

using namespace std;
const int maxn = 105;
typedef long long ll;
const ll mod = 1e9+7;

int N, v[maxn];
ll dp[maxn][maxn], C[maxn][maxn];

void init (int n) {
	for (int i = 0; i <= n; i++) {
		C[i][0] = C[i][i] = 1;
		for (int j = 1; j < i; j++)
			C[i][j] = (C[i-1][j-1] + C[i-1][j]) % mod;
	}
}

int solve() {
	memset(dp, 0, sizeof(dp));
	for (int i = 1; i <= N; i++)  dp[i][i] = 1;
	for (int len = 1; len < N; len++) {
		for (int l = 1; l + len <= N; l++) {
			int r = l + len;
			for (int k = l; k <= r; k++) {
				if (k == l)
					dp[l][r] = (dp[l][r] + dp[k+1][r]) % mod;
				else if (k == r)
					dp[l][r] = (dp[l][r] + dp[l][k-1]) % mod;
				else if (v[k-1] == v[k+1])
					dp[l][r] = (dp[l][r] + dp[l][k-1] * dp[k+1][r] % mod * C[r-l][k-l] % mod) % mod;
			}
		}
	}
	return dp[1][N];
}

int main () {
	init(100);
	while (scanf("%d", &N) == 1) {
		for (int i = 1; i <= N; i++)
			scanf("%d", &v[i]);
		printf("%d\n", solve());
	}
	return 0;
}


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved