考察:区间dp
这题没做出来,要不我还是别学OI了...
思路:
f[i][j]表示[i,j]区间内取得的最小值.集合划分就是以中断点为标准,k = i+1,i+2...j-1...f[i][j] = min(f[i][k]+f[k][j]+a[i]*a[k]*a[j])
为什么是a[i]*a[k]*a[j]呢?f[i][k]考虑将(i,k)区间内的数取完,同理k,j.两边的数就明显是i,j了.
1 #include <iostream> 2 #include <cstring> 3 #include <algorithm> 4 #include <cstdio> 5 using namespace std; 6 const int N = 110; 7 int a[N],f[N][N]; 8 int main() 9 { 10 int n; 11 scanf("%d",&n); 12 for(int i=1;i<=n;i++) scanf("%d",&a[i]); 13 for(int len=3;len<=n;len++) 14 for(int l=1;l+len-1<=n;l++) 15 { 16 int r = l+len-1; 17 f[l][r] = 0x3f3f3f3f; 18 for(int k=l+1;k<r;k++) 19 f[l][r] = min(f[l][k]+f[k][r]+a[l]*a[k]*a[r],f[l][r]); 20 } 21 printf("%d\n",f[1][n]); 22 return 0; 23 }
Multiplication Puzzle POJ - 1651
原文：https://www.cnblogs.com/newblg/p/14398272.html