1 条题解

  • 1
    @ 2017-12-03 17:24:59
    #include <cmath>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <iomanip>
    #include <iostream>
    #include <algorithm>
    #include <vector>
    #include <deque>
    #include <set>
    #include <limits>
    #include <string>
    #include <sstream>
    #include <thread>
    using namespace std;
    
    const int oo_min=0xc0c0c0c0,oo_max=0x3f3f3f3f;
    
    namespace dts
    {
        int n,m;
        int a[1000+1+1];
        int sum[1000+1+1];
        int c[1000+1+1][1000+1+1];
        int f[1000+1+1][1000+1+1];
        int s[1000+1+1][1000+1+1];
        void pr_dp()
        {
            memset(sum,0,sizeof(sum));
            for (int i=1;i<=n;i++)
                sum[i]=sum[i-1]+a[i];
            memset(c,0,sizeof(c));
            for (int i=1;i<=n;i++)
                for (int j=i;j<=n;j++)
                    c[i][j]=c[i][j-1]+(a[j]*(sum[j-1]-sum[i-1]));
            memset(f,oo_max,sizeof(f));
            memset(s,0,sizeof(s));
            for (int i=0;i<=n;i++)
            {
                s[i][0]=0;
                s[n+1][i]=n;
                f[i][0]=c[1][i];
            }
        }
        int pro_dp()
        {
            for (int i=1;i<=m;i++)
                for (int j=n;j>=1;j--)
                    for (int k=s[j][i-1];k<=s[j+1][i];k++)
                        if (f[k][i-1]+c[k+1][j]<f[j][i])
                        {
                            s[j][i]=k;
                            f[j][i]=f[k][i-1]+c[k+1][j];
                        }
            return f[n][m];
        }
        void main()
        {
            while (~scanf("%d%d",&n,&m))
                if (n>0&&m>0)
                {
                    for (int i=1;i<=n;i++)
                        scanf("%d",&a[i]);
                    pr_dp();
                    printf("%d\n",pro_dp());
                }
                else
                    break;
        }
    };
    
    int main()
    {
        dts::main();
    }
    
  • 1

Lawrence(题面原来就是英文,不是我改的)

信息

难度
9
分类
动态规划 点击显示
标签
(无)
递交数
7
已通过
3
通过率
43%
上传者