The goal is to take cards in such order as to minimize the total number of scored points.
For example, if cards in the row contain numbers 10 1 50 20 5, player might take a card with 1, then 20 and 50, scoring
10?1?50+50?20?5+10?50?5=500+5000+2500=800010?1?50+50?20?5+10?50?5=500+5000+2500=8000
If he would take the cards in the opposite order, i.e. 50, then 20, then 1, the score would be
1?50?20+1?20?5+10?1?5=1000+100+50=1150.1?50?20+1?20?5+10?1?5=1000+100+50=1150.
题意：
n个数相乘，每次从中抽取一个数出来与相邻两个数相乘，直到抽到只剩两个数字，第一个数和最后一个数不能抽，求和最小值。
思路：
定义dp[i][j]dp[i][j]为从i到j取数后值得最小值，枚举k?(i,j)k?(i,j)，表示从i到j最后抽取第k个数字， (注意：i,j不取)
状态转移方程为
dp[st][ed]=min(dp[st][ed],dp[st][k]+dp[k][ed]+a[st]*a[k]*a[ed]);注意dp数组的初始化：边界扫不到的地方为0，其他初始为inf
代码：
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=1006;
int a[maxn];
int dp[maxn][maxn];
int main(){int t;scanf("%d",&t);for(int i=1;i<=t;i++){scanf("%d",&a[i]);}memset(dp,0,sizeof(dp));for(int l=3;l<=t;l++){for(int st=1;st<=t-l+1;st++){int ed=st+l-1;dp[st][ed]=0x3f3f3f3f;for(int k=st+1;k<ed;k++){dp[st][ed]=min(dp[st][ed],dp[st][k]+dp[k][ed]+a[st]*a[k]*a[ed]);}}}printf("%d\n",dp[1][t]);
}