ZOJ 1602 Multiplication Puzzle(矩陣連乘)

題意:給出一排卡,每次能拿走除了第一張和最後一張之外的任何卡,拿走卡i之後要加上卡i和卡i-1和卡i+1的乘積,直到剩下第一張和最後一張為止,求最少的乘積和.

設dp[i][j]為拿走i..j之間卡的最少乘積和,那麼答案就是dp[1][N]

dp[i][j] = min{dp[i][k[ + dp[k][j] + C[i] * C[k] * C[j]] | i< k < j}

base cases: dp[i][i] = 0, dp[i][i + 1] = 0.

#include 
#include 
#include 
using namespace std;
const int MAX = 105;

int main(int argc, char const *argv[]){
	int dp[MAX][MAX];
	int cards[MAX];
	int N;
	while(scanf("%d", &N) == 1){
		memset(dp, 0x20, sizeof(dp));
		for(int i = 1; i <= N; ++i){
			scanf("%d", &cards[i]);
			dp[i][i] = dp[i][i + 1] = 0;
		}

		for(int p = 2; p < N; ++p){
			for(int i = 1; i <= N && i + p <= N; ++i){
				int j = i + p;
				for(int k = i; k <= j; ++k){
					dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + cards[i] * cards[k] * cards[j]);
				}
			}
		}

		printf("%d\n", dp[1][N]);
	}
	return 0;
}