20min写完,没过样例,然后发现循环边界弄错了/kk
区间 dp 。
设 f[i][j] 表示从 i 到 j 这个区间取走除两端外所有牌后的最小答案。
对于从 i 到 j 的区间,我们可以枚举一个分解点 k ,则答案由 f[i][k] 和 f[k][j] 转移而来。即我们可以先取走 i 到 k 之间的牌,再取走 k 到 j 之间的牌,最后取走 k ,就只剩下了 i 和 j 两张牌。
所以状态转移方程即为 f[i][j] = min(f[i][j],f[i][k]+f[k][j]+a[i]*a[k]*a[j]) 。
因为要保证 f[i][k] 和 f[k][j] 在 f[i][j] 被求之前就已经求过,所以循环的时候要先枚举长度 l ,在枚举左端点 i ,求出 j = i + l - 1。
注意不要把循环边界写错了,左端点要枚举到 n - l + 1 。
#include<bits/stdc++.h> using namespace std; int f[101][101],n,a[101]; int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { f[i][j]=2e9;//因为要求最小值,所以必须赋初始值 } } for(int i=1;i<=n;i++) { scanf("%d",&a[i]); f[i][i+1]=0;//显然当区间为连续的两张牌时代价为0 } for(int l=3;l<=n;l++)//枚举长度 { for(int i=1;i<=n-l+1;i++)//枚举左端点 { int j=i+l-1;//求出右端点 for(int k=i+1;k<j;k++)//枚举分界点 { f[i][j]=min(f[i][j],f[i][k]+f[k][j]+a[i]*a[k]*a[j]); } } } cout<<f[1][n]<<endl; return 0; }