测试数据来自 sky1231/5b0018bad3d8a103c03e0651

背景

劳伦斯在第一次世界大战期间是个有争议的人物，他是一名英国军官，曾在阿拉伯剧院工作，带领一群阿拉伯人在游击战中反抗奥斯曼帝国。他的主要目标是铁路。他的功绩的一个高度虚构的版本出现在大片《阿拉伯的劳伦斯》中。

问题描述

你需要编写一个程序来帮助劳伦斯找出如何最好地利用有限的资源。你有一些来自英国情报部门的信息。首先，轨道线是完全线性的——没有分支，没有热刺。接下来，英国情报部门对每个仓库都有一个战略重要性——从1到100。一个仓库本身就没有用处，它只有在与其他仓库相连的时候才有价值。整个铁路的战略价值是通过增加每对连接的仓库的战略价值的产品，直接或间接地，通过铁路。考虑一下这个铁路:

它的战略价值是4*5+4*1+4*2+5*1+5*2+1*2=49。
现在，假设劳伦斯只有足够的资源来进行一次攻击。他不能自己攻击仓库——他们防守得太好了。他必须攻击沙漠中间的铁路线。想想如果劳伦斯在中间攻击这条铁路线会发生什么:

剩余铁路的战略价值是4*5+1*2=22。但是，假设劳伦斯在4到5个库之间进行攻击:

剩余铁路的战略价值是5*1+5*2+12=17。这是劳伦斯的最佳选择。
考虑到铁路的描述和劳伦斯可以执行的攻击数量，找出他能实现的最小的战略价值。

格式

输入

将会有几个数据集。每个数据集将开始与两个整数,n和m。n在铁路仓库的数量(1≤n≤1000)和m是劳伦斯的攻击数量参考资料(0≤m<n)。下一行将是n个整数，每一个从1到100，说明每个仓库的战略价值。输入端将以n=0和m=0的一行为标记，而m=0则不应被处理。

输出

对于每一个数据集，输出一个整数，说明劳伦斯在攻击时所能达到的铁路的最小战略价值。将每个整数输出到自己的行中。

C++ Code

#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();
}

Source

Vijos Original