题意:给出一排卡,每次能拿走除了第一张和最后一张之外的任何卡,拿走卡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; }