记录编号	416178	评测结果	AAAAAAA
题目名称	[HZOI 2014] 合并石子	最终得分	100
用户昵称	kZime	是否通过	通过
代码语言	C++	运行时间	0.005 s
提交时间	2017-06-20 08:01:09	内存使用	0.80 MiB

# include <bits/stdc++.h>
# define MAXN 102
using namespace std;

inline char getc() { 
    static char buf[1 << 18], *fs, *ft;
    return (fs == ft && (ft = (fs = buf) + fread(buf, 1, 1 << 18, stdin)), fs == ft) ? EOF : *fs++;
}

inline int gn() { 
    register int k = 0, f = 1;
    register char c = getc();
    for(; !isdigit(c); c = getc()) if(c == '-') f = -1;
    for(; isdigit(c); c = getc()) k = k * 10 + c - '0';
    return k * f;
}

int s[MAXN << 1][MAXN], f[MAXN << 1][MAXN], fm[MAXN << 1][MAXN], w[MAXN << 1], n, ani = 0x7fffffff, anx;//s[i][j]是区间和

inline void merge_stone() { 
    for(int r = 1; r < n; r++) { 
        for(int i = 1; i <= (n << 1) - r; i++) { 
            int j = r + i;
            fm[i][j] = 0x7fffffff;
            for(int k = i; k < j; k++) { 
                f[i][j] = max(f[i][j], f[i][k] + f[k + 1][j] + s[i][j]);
                fm[i][j] = min(fm[i][j], fm[i][k] + fm[k + 1][j] + s[i][j]);
            }
        }
    }
    for(int i = 1; i <= n; i++) { 
        anx = max(anx, f[i][i + n - 1]);
        ani = min(ani, fm[i][i + n - 1]);
    }
}

int main() { 
# ifndef LOCAL
    freopen("stone2.in", "r", stdin);
    freopen("stone2.out", "w", stdout);
# else
    freopen("in", "r", stdin);
# endif
    n = gn();
    for(int i = 1; i <= n; i++) { 
        w[i + n] = w[i] = gn();
    }
    for(int i = 1; i <= (n << 1); i++) { 
        s[i][i] = w[i];
        for(int j = i + 1; j <= (n << 1); j++) { 
            s[i][j] = s[i][j - 1] + w[j];
        }
    }
    merge_stone();
    printf("%d\n%d\n", ani, anx);
}