BZOJ 4897: [Thu Summer Camp2016]成绩单 动态规划

#include <cstdio>  
#include <cstring>
#include <algorithm>  
#define N 52    
#define setIO(s) freopen(s".in", "r" , stdin)   
int w[N], v[N], f[N][N], g[N][N][N][N];  
inline void getmin(int &a, int b) 
{
    if(b < a) a = b;    
}   
int main() 
{
    // setIO("input");  
    int n, A, B, i, j, len; 
    scanf("%d%d%d", &n , &A, &B), memset(f, 0x3f, sizeof(f)), memset(g, 0x3f, sizeof(g));         
    for(i = 1; i <= n ; ++ i) scanf("%d", &w[i]), v[i] = w[i];  
    std :: sort(v + 1, v + 1 + n);       
    for(i = 1; i <= n ; ++ i) 
    {
        w[i] = std :: lower_bound(v + 1, v + 1 + n, w[i]) - v; 
        f[i][i] = A, g[i][i][w[i]][w[i]] = 0;      
    }               
    for(len = 2; len <= n ; ++ len) 
    {
        int l, r, k; 
        for(l = 1; l + len - 1 <= n ; ++ l) 
        {
            r = l + len - 1;    
            for(i = 1; i <= n ; ++ i) 
            {
                for(j = i; j <= n ; ++ j) 
                    getmin( g[l][r][std :: min(i, w[r])][std :: max(j, w[r])], g[l][r - 1][i][j]);    
            }    
            for(k = l; k < r ; ++ k)  
            {
                for(i = 1; i <= n ; ++ i) 
                    for(j = i; j <= n ; ++ j) 
                            getmin(g[l][r][i][j], g[l][k][i][j] + f[k + 1][r]);        
            }               
            for(i = 1; i <= n ; ++ i) 
            {
                for(j = i; j <= n ; ++ j) 
                    getmin(f[l][r], g[l][r][i][j] + A + B * (v[j] - v[i]) * (v[j] - v[i]));        
            }
        }
    }
    printf("%d\n", f[1][n]);     
    return 0; 
}