题目链接

分析： 这道题看上去挺难

正在发呆的时候，突然想到能量项链 潜意识告诉我这也是一道区间dp

那就类比一下能量项链（合并石子） 合并石子的状态设计是 f[i][j]表示(i,j)的石子合成一堆的获益 f[i][j]=max{f[i][k]+f[k+1][j]+sum(i,j)} (sum是区间和)

这道题是取纸牌，其实取掉纸牌可以看做进行了合并 我们设计状态 f[i][j]表示拿走了(i,j)中的所有牌，不包括i和j 所获得的最大收益

转移：f[i][j]=min{f[i][k]+f[k][j]+num[i]*num[k]*num[j]}

tip

初始化: f[i][i]=f[i][i+1]=0 注意循环的顺序

遵循原则：当前状态是从稳定状态转移而来

这里写代码片 #include<cstdio> #include<iostream> #include<cstring> using namespace std; int f[101][101]; //f[l][r]把(l,r)都取走后的最小值 int num[101],n; void doit() { int i,j,k,l,s; memset(f,0x33,sizeof(f)); for (i=1;i<=n;i++) f[i][i]=0,f[i][i+1]=0,f[i-1][i]=0; //实在太懒，就这样随意初始化一下 for (i=n-2;i>=1;i--) for (j=i+2;j<=n;j++) for (k=i+1;k<j;k++) f[i][j]=min(f[i][j],f[i][k]+f[k][j]+num[i]*num[j]*num[k]); printf("%d",f[1][n]); } int main() { scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%d",&num[i]); doit(); return 0; }