poj 1651 Multiplication Puzzle (区间dp)

poj 1651题目链接

题意:n个数,删掉a[i]的得分是a[i]*a[i-1]*a[i+1],两个端点的不允许删。问删完n-2个数得到的最小分数是多少。

思路:能想到设计状态dp[i][j]表示区间[i,j]的最小分数。然后就没思路了。 T T

参考了几篇题解,思路大概是,枚举最后剩下的那个数。

对于一个区间(l, r),如果最后删除的是k位置的数的话,将得到a[l]*a[k]*a[r]分,而要得到这个情况的前提是吧区间(l, k) 和(k, r)的中间数字删掉所以的转移方程是

DP(l, r) = DP(l, k) + DP(k, r) + a[l]*a[k]*a[r];

以及。。。初始化又想错了。。。

要注意。。初始化可能没办法一次完成。。。这道题的初始化就是分情况的。。。

对于区间长度不够的。。初始化为0.。

区间长度为3的。。初始化为a[i]*a[i+1]*a[i+2]。。

其他的初始化为正无穷。。

 

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz