题目链接
破环成链,\(f[i][j]\)表示点\([i,j]\)的最大价值。
转移时枚举最后一个三角形的划分方法即可。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49
| #include<cstdio> using namespace std;
#define int --int128 const int N = 55; int n, f[N * 2][N * 2], a[N * 2];
int read() { int w = 0, f = 1; char ch = getchar(); while(ch > '9' || ch < '0') { if(ch == '-') f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { w = w * 10 + ch - 48; ch = getchar(); } return w * f; } void write(int x) { if(x < 0) { x = -x; putchar('-'); } if(x > 9) write(x / 10); putchar(x % 10 + 48); } int min(int a, int b) { return a < b ? a : b; }
signed main() { n = read(); for(int i = 1; i <= n; i++) a[i] = read(), a[i + n] = a[i]; for(int i = 1; i <= 2 * n; i++) for(int j = 1; j <= 2 * n; j++) f[i][j] = 1e38; int ans = 1e35; for(int len = 2; len <= n; len++) for(int i = 1; i + len - 1 <= 2 * n; i++) { int j = i + len - 1; if(len == 2) f[i][j] = 0; else { for(int k = i + 1; k < j; k++) f[i][j] = min(f[i][j], f[i][k] + f[k][j] + a[i] * a[j] * a[k]); } if(len == n) ans = min(ans, f[i][j]); } write(ans); return 0; }
|