题意：一串数，每次取掉一个数并且将这个数与周围两个数相乘的结果加起来，最后取得就剩两个数。求最小的答案。
解答：区间dp。在网上看到两个答案：
第一种思路：dp[i][j]表示从i-1到j最终取得就剩下i-1和j所得的最小值。那么状态转移方程为dp[i][j] = min(dp[i][j],dp[i][k]+dp[k+1][j]+a[k]*a[i-1]*a[j])(i <= k < j)
代码：
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; const int MAXN = 150; const int INF = 1 << 30; int dp[MAXN][MAXN]; int main() { int n,a[MAXN]; while(~scanf("%d",&n)) { for(int i = 1;i <= n;i++) scanf("%d",&a[i]); for(int i = 1;i <= n;i++) for(int j = 1;j <= n;j++) dp[i][j] = 0; for(int l = 2;l <= n-1;l++) for(int i = 2;i + l - 1 <= n;i++) { int j = i + l - 1; dp[i][j] = INF; for(int k = i;k < j;k++) dp[i][j] = min(dp[i][j],dp[i][k] + dp[k+1][j] + a[k]*a[i-1]*a[j]); } printf("%d\n",dp[2][n]); } return 0; }
第二种思路：dp[i][j]表示从i到jj到最终取得就剩下i和j所得的最小的值
因此状态转移方程为:dp[i][j] = min(dp[i][j],dp[i][k] + dp[k][j] + a[k] * a[i] * a[j])（i < k < j）
代码：
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; const int MAXN = 150; const int INF = 1 << 30; int dp[MAXN][MAXN]; int main() { int n; int a[MAXN]; while(~scanf("%d",&n)){ for(int i = 1;i <= n;i++) scanf("%d",&a[i]); memset(dp,0,sizeof(dp)); for(int l = 3;l <= n;l++) for(int i = 1;i + l - 1 <= n;i++) { int j = i + l - 1; dp[i][j] = INF; for(int k = i + 1;k < j;k++) dp[i][j] = min(dp[i][j],dp[i][k] + dp[k][j] + a[i]*a[j]*a[k]); } printf("%d\n",dp[1][n]); } return 0; }