1 条题解
-
1
#include <algorithm> using namespace std; typedef long long ll; const int MAXN = 505; const ll INF = 1e18; ll dp[MAXN][MAXN]; int main() { int n; cin >> n; // len=2,两点,代价0 for(int i = 1; i <= n; ++i) dp[i][i+1] = 0; // len:区间点的数量,从3到n for(int len = 3; len <= n; ++len) { for(int i = 1; i + len - 1 <= n; ++i) { int j = i + len - 1; dp[i][j] = INF; // 枚举分割点k for(int k = i+1; k < j; ++k) { ll val = dp[i][k] + dp[k][j] + 1LL * i * k * j; dp[i][j] = min(dp[i][j], val); } } } cout << dp[1][n] << endl; return 0; }
- 1
信息
- ID
- 1885
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 5
- 标签
- (无)
- 递交数
- 147
- 已通过
- 55
- 上传者