HDU 4283 You Are the One （区间DP，经典）

题意：

　　某校举行一场非诚勿扰，给定一个出场序列，表示n个人的屌丝值，如果他是第k个出场的，他的不满意度为(k-1)*diao[i]。为了让所有人的屌丝值之和更小，导演设置一个栈，可以将部分人装进栈中，来改变序列。也就是说，要么按照给定序列上场，要么将某个人前面部分人装进栈，让该人先出场，再让栈中的人出场，都行。问屌丝值之和最少可以是多少？

思路：

　　想挫了，哎～

　　如果考虑区间p[1->n]的出场次序时，只考虑p[1]是第几个出场的就行了，假设是第k个，那么区间p[2->k]就必须比p[1]先出场（想想为什么），而p[k+1->n]就在p[1]之后出场了。那么不就分成了两个子问题了吗？只要在处理[L,R]时保证其任一子区间都已经考虑过了，就可以完成转移了。比p[j]后出场的，整个区间的dp值要上升了，因为他们的出场顺序变成k+1~n了。

//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <map>
#include <algorithm>
#include <vector>
#include <iostream>
#define pii pair<int,int>
#define INF 0x7f3f3f3f
#define LL long long
using namespace std;
const double PI  = acos(-1.0);
const int N=110;

int d[N], dp[N][N], sum[N], n;

int cal()
{
    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 j=2; j<=n; j++)
    {
        for(int i=j-1; i>0; i--)
        {
            for(int k=0; k<=j-i; k++) //考虑让d[i]成为第k+1个出场
            {
                int t= d[i]*k + dp[i+1][i+k] + dp[i+k+1][j]+(k+1)*(sum[j]-sum[i+k]);
                dp[i][j]=min(dp[i][j], t );
            }
        }
    }
    return dp[1][n];
}

int main()
{
    freopen("input.txt", "r", stdin);
    int t, Case=0;cin>>t;
    while( t-- )
    {
        sum[0]=0;
        scanf("%d",&n);
        for(int i=1; i<=n; i++)
        {
            scanf("%d",&d[i]);
            sum[i]=sum[i-1]+d[i];
        }
        printf("Case #%d: %d
",++Case, cal());
    }
    return 0;
}