这是神题,n <= 1000,如果是极限数据普通的n^3区间DP怎么可能过?可偏偏就过了。
刘汝佳大哥的训练指南上面说的存在nlgn的算法解决矩阵链乘问题,可是百度都找不到。。。。
AC代码
#include <cstdio> #include <cmath> #include <algorithm> #include <cstring> #include <utility> #include <string> #include <iostream> #include <map> #include <set> #include <vector> #include <queue> #include <stack> using namespace std; #pragma comment(linker, "/STACK:1024000000,1024000000") #define eps 1e-10 #define inf 0x3f3f3f3f #define PI pair<int, int> typedef long long LL; const int maxn = 1000 + 5; const LL INF = 1e15; LL d[maxn][maxn]; int n, w[maxn]; LL solve() { //初始化边界 for(int i = 0; i < n; ++i) d[i][i] = 0; for(int l = 2; l <= n; ++l) { for(int i = 0; i <= n-l; ++i) { int j = i + l - 1; d[i][j] = INF; LL m = w[i] * w[j+1], h; //优化常数 for(int k = i; k < j; ++k) { h = d[i][k] + d[k+1][j] + w[k+1]*m; if(h < d[i][j]) d[i][j] = h; } } } return d[0][n-1]; } int main() { while(scanf("%d", &n) == 1) { for(int i = 0; i <= n; ++i) scanf("%d", &w[i]); printf("%lld\n", solve()); } return 0; }
如有不当之处欢迎指出!