还是有点蒙，先附上别人的题解
原文链接：https://blog.csdn.net/u014141559/article/details/38035603
题意：
有一个队列，每个人有一个愤怒值D，如果他是第K个上场，不开心指数就为(K-1)*D。但是边上有一个小黑屋（其实就是个堆栈），可以一定程度上调整上场程序
<span style="font-size:18px;">#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> using namespace std; int dp[110][110]; int a[110],sum[110]; int n; int solve(int i,int j) { int &ans=dp[i][j]; if(ans!=-1) return ans; if(i>=j) return 0; ans=1<<30; for(int k=1;k<=j-i+1;k++){ ans=min(ans,solve(i+1,i+k-1)+solve(i+k,j)+(k-1)*a[i]+(sum[j]-sum[i+k-1])*k); } return ans; } int main() { int t,iCase=1; cin>>t; while(t--){ cin>>n; sum[0]=0; for(int i=1;i<=n;i++){ scanf("%d",&a[i]); sum[i]=sum[i-1]+a[i]; } memset(dp,-1,sizeof dp); printf("Case #%d: %d\n",iCase++,solve(1,n)); } return 0; }</span>
递推式 0MS
<span style="font-size:18px;">#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #define maxn 110 #define inf 0x7fffffff using namespace std; int dp[maxn][maxn]; int sum[maxn]; int a[maxn]; int n; int main() { int t,iCase=1; scanf("%d",&t); while(t--){ sum[0]=0; scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); sum[i]=sum[i-1]+a[i]; } memset(dp,0,sizeof dp); for(int i=1;i<=n;i++){ for(int j=i+1;j<=n;j++){ dp[i][j]=inf; } } for(int p=1;p<=n;p++){ for(int i=1;i<=n-p+1;i++){ int j=i+p-1; for(int k=1;k<=p;k++){ dp[i][j]=min(dp[i][j],dp[i+1][i+k-1]+dp[i+k][j]+(k-1)*a[i]+(sum[j]-sum[i+k-1])*k); } } } printf("Case #%d: %d\n",iCase++,dp[1][n]); } return 0; }</span>
原文：https://www.cnblogs.com/lijiahui-123/p/13332729.html