题解

1 条题解

  • 0
    @ 2018-07-20 14:47:58

    #include <cstdio>
    using namespace std;
    const int maxn = 13005;
    int m[maxn][maxn];
    int a[maxn][maxn],cost[maxn];
    int N,A,i,j;

    int te;
    int main()
    {
    scanf("%d",&N);
    cost[0]=0;

    for(i=1;i<=N;i++)
    {
    scanf("%d",&cost[i]);
    cost[i]+=cost[i-1];
    }
    for(i=1;i<=N;i++)
    {
    m[i][i]=0;
    a[i][i]=i;
    }
    for(i=N;i>=1;i--)
    {
    for(j=i+1;j<=N;j++)
    {
    int ans=1<<29;
    for(int k=a[i][j-1];k<=a[i+1][j];k++)
    {
    if(ans>m[i][k]+m[k+1][j]+cost[j]-cost[i-1])
    {
    ans=m[i][k]+m[k+1][j]+cost[j]-cost[i-1];
    te=k;
    }
    }
    m[i][j]=ans;
    a[i][j]=te;
    }

    }
    printf("%d",m[1][N]);
    return 0;
    }
    题有问题没法ac

    • @ 2018-10-02 17:38:22

      这个方法时间复杂度是O(n^3),会超时,同时a与m数组的大小也会导致超内存。

  • 1

信息

难度
9
分类
(无)
标签
递交数
344
已通过
8
通过率
2%
上传者