区间dp

这一题我没有做出来

关键是我想不到，如何设置断点。
因此我就无法写出状态转移方程。
正确答案中的断点设置是dp[i][j] 枚举i是第k个出场的

这真的十十分的巧妙

换句话说，既然是区间dp那么就一定是可以设置断点的。

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int inf = 1e9;
int n,a[110],dp[110][110],sum[110];
int main(){
    int T;scanf("%d",&T);
    for (int tcase=1;tcase<=T;++tcase){
        scanf("%d",&n);
        for (int i=1;i<=n;++i)scanf("%d",&a[i]);
        for (int i=1;i<=n;++i)sum[i]=sum[i-1]+a[i];
        for (int p=1;p<=n;++p){
            for (int i=1,j=i+p-1;j<=n;++i,++j){
                dp[i][j]=inf;
                for (int k=1;k<=p;++k){
                    dp[i][j]=min(dp[i][j],dp[i+1][i+k-1]+(k-1)*a[i]+dp[i+k][j]+(sum[j]-sum[i+k-1])*k);
                }
            }
        }printf("Case #%d: %d\n",tcase,dp[1][n]);
    }
}