题目链接

http://poj.org/problem?id=1651

解题思路

比较简单，就是板子题稍微改了改转移方程。
每次这种题，如果你想不出[i,k]和[k+1,j]与[i,j]的关系，你就想你要枚举的k的意义是什么，确定了k的意义之后就方便建立转移方程了。
比如这个题，首先可以确定的是dp[i][j]表示[i,j]最少得分，最后留下左端点i和右端点j。
直接去想[i,k]和[k+1,j]与[i,j]的关系，我想了许久都没想出来；
换了换思路，思考k在枚举什么，k不就在枚举一个分界点，把区间[i,j]分成两部分，计算分成两部分后的最少得分。咋算，不难吧， 左边部分的最少得分+右边部分的最少得分，这是在转移到[i,j]之前已经算好的，再有一部分是左边部分留下个右端点，右边部分留下个左端点，这俩点是一个点，就是我们枚举的k，也就是说现在剩下三个点，i，k，j，这三个点的得分只有一种组合a[i]*a[k]*a[j]。
所以，综上三部分得出转移方程dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+a[i]*a[k]*a[j])
但是样例一跑为啥不对？
上面也说了，k是枚举左边部分的右端点，右边部分的左端点，因此转移方程应该为：dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]+a[i]*a[k]*a[j])，这样才能剩下i，k，j；如果按照上面的转移方程转移的话，左边部分算完，右边部分算完，剩下的是i，k，k+1，j，这之后就还得再进行转移才能得到正确的结果，但是完全可以放在一次转移中实现。
这打破了找[i,k]和[k+1,j]与[i,j]的关系的思维定势，很显然，这里的右半部分的左端点不是k+1，而是k。
所以，找k的物理意义未尝不是个好办法。

AC代码

//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=110;
const int inf=0x3f3f3f3f;
int dp[N][N],a[N],n;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int len=3;len<=n;len++)
        for(int i=1;i+len-1<=n;i++){
            int j=i+len-1;
            dp[i][j]=inf;
            for(int k=i+1;k<j;k++)
                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]+a[k]*a[i]*a[j]);
        }
    cout<<dp[1][n]<<endl;
} 

总结

终于自己做出来一道区间dp题了，我太难了，一直不会，可算做出个简单的了，要不我心态都崩了。