题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4283
自己想了很久还是不会，参考了别人的思路才写的，区间DP还是很弱，继续努力！！
思路：
转载：
题解：想dp[i][j]表示[i ,j]内的unhappiness最小值，枚举k（i<=k<j），有两种情况需要讨论：
1 如果[i , k]区间内的人全部在[k+1, j]区间内的人之前出列，且已经全部不在栈中，即[i , j]区间可以分为[i , k] , [k+1 ,j]两个完全相同的子问题，
即dp[i][j] =MIN(dp[i][j] , dp[i][k] + dp[k+1][j] + (sum[j] – sum[i]) * (k – i +１));
2 如果[i , k]区间内的人全部在[k+1 , j]区间内的人之后出列，即[i , k]区间内的人全部需要进栈，所以出来的顺序是逆序的，需O（n2）预处理出against_order[i][j]
表示[i , j]区间人逆序出来的unhappiness值，即dp[i][j] = MIN(dp[i][j] , dp[k+1][j] + against_order[i][k] + (sum[k]– sum[i-1]) * (j - k));
我用了记忆化搜索和迭代两种方式实现，主要是为了加深自己的理解和记忆
记忆化搜索代码 ：
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
using namespace std;
#define INF 1000010111
int n;
int a[];
int dp[][];
int sum[];
int order[][];
void Make_order()
{
memset(order,,sizeof(order));
for(int j=;j<=n;j++)
for(int i=j-;i>=;i--)
order[i][j]=order[i+][j]+a[i]*(j-i); }
int dfs(int i,int j)
{
if(dp[i][j]<INF) return dp[i][j];
if(i==j) return dp[i][j]=;
for(int k=i;k<j;k++)
dp[i][j]=min(dp[i][j],min(dfs(i,k)+dfs(k+,j)+(sum[j]-sum[k])*(k-i+),dp[k+][j]+order[i][k]+(sum[k]-sum[i-])*(j-k)));
return dp[i][j];
}
int main()
{
int t;
scanf("%d",&t);
int tol=;
while(t--)
{
sum[]=;
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%d",&a[i]);
sum[i]=sum[i-]+a[i];
}
Make_order();
for(int i=;i<;i++)
for(int j=;j<;j++)
dp[i][j]=INF;
cout<<"Case #"<<tol++<<": "<<dfs(,n)<<endl;
} }
迭代代码：
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
using namespace std;
#define INF 100001000
int dp[][];
int a[];
int sum[];
int order[][];
int n;
void init()
{
scanf("%d",&n);
sum[]=;
for(int i=;i<=n;i++)
{
scanf("%d",&a[i]);
sum[i]=sum[i-]+a[i];
}
for(int i=;i<;i++)
for(int j=i;j<;j++)
if(i==j) dp[i][j]=;
else dp[i][j]=INF;
memset(order,,sizeof(order));
for(int j=;j<=n;j++)
for(int i=j-;i>=;i--)
order[i][j]=order[i+][j]+a[i]*(j-i);
} int main()
{
int t;
int tol=;
scanf("%d",&t);
while(t--)
{
init();
for(int j=;j<=n;j++)
for(int i=j-;i>=;i--)
{
for(int k=i;k<j;k++)
dp[i][j]=min(dp[i][j],min(dp[i][k]+dp[k+][j]+(sum[j]-sum[k])*(k-i+),dp[k+][j]+order[i][k]+(sum[k]-sum[i-])*(j-k)));
}
cout<<"Case #"<<tol++<<": "<<dp[][n]<<endl;
}
return ; }