HDU 4283 You Are the One

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long LL;
const LL INF = 0xfffffff;
const LL maxn = 105;
int dp[maxn][maxn], a[maxn], sum[maxn];

int DFS(int L,int R)
{
    if(dp[L][R])
        return dp[L][R];
    if(L > R)
        return 0;

    dp[L][R] = INF;
    for(int k=0; k<=R-L; k++)///在区间【L,R】内，这个数该如何去选择
    {///假设第L个数字，要在第K次选择
        dp[L][R] = min(dp[L][R], DFS(L+1, L+k) + a[L]*k + DFS(L+k+1,R) + (sum[R]-sum[L+k])*(k+1) );
    }
   // printf("dp[%d][%d]:%d\n",L, R, dp[L][R]);
    return dp[L][R];
}
/*
第L个元素第k个出场拍，
*/
int main()
{
    int T, n, cas = 1;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d", &n);
        memset(dp, 0, sizeof(dp));
        for(int i=0; i<n; i++)
            scanf("%d", &a[i]);
        sum[0] = a[0];

        for(int i=1; i<n; i++)
            sum[i] = sum[i-1] + a[i];

        printf("Case #%d: %d\n",cas ++, DFS(0, n-1));
    }
    return 0;
}

/*
2
2
4 5


2
5
1 2 3 4 5

5
5 4 3 2 2
*/