Background

T. E. Lawrence was a controversial figure during World War I. He was a British officer who served in the Arabian theater and led a group of Arab nationals in guerilla strikes against the Ottoman Empire. His primary targets were the railroads. A highly fictionalized version of his exploits was presented in the blockbuster movie, "Lawrence of Arabia".

Description

You are to write a program to help Lawrence figure out how to best use his limited resources. You have some information from British Intelligence. First, the rail line is completely linear---there are no branches, no spurs. Next, British Intelligence has assigned a Strategic Importance to each depot---an integer from 1 to 100. A depot is of no use on its own, it only has value if it is connected to other depots. The Strategic Value of the entire railroad is calculated by adding up the products of the Strategic Values for every pair of depots that are connected, directly or indirectly, by the rail line. Consider this railroad:

Its Strategic Value is 4*5+4*1+4*2+5*1+5*2+1*2=49.
Now, suppose that Lawrence only has enough resources for one attack. He cannot attack the depots themselves---they are too well defended. He must attack the rail line between depots, in the middle of the desert. Consider what would happen if Lawrence attacked this rail line right in the middle:

The Strategic Value of the remaining railroad is 4*5+1*2=22. But, suppose Lawrence attacks between the 4 and 5 depots:

The Strategic Value of the remaining railroad is 5*1+5*2+12=17. This is Lawrence's best option.
Given a description of a railroad and the number of attacks that Lawrence can perform, figure out the smallest Strategic Value that he can achieve for that railroad.

Format

Input

There will be several data sets. Each data set will begin with a line with two integers, n and m. n is the number of depots on the railroad (1≤n≤1000), and m is the number of attacks Lawrence has resources for (0≤m<n). On the next line will be n integers, each from 1 to 100, indicating the Strategic Value of each depot in order. End of input will be marked by a line with n=0 and m=0, which should not be processed.

Output

For each data set, output a single integer, indicating the smallest Strategic Value for the railroad that Lawrence can achieve with his attacks. Output each integer in its own line.

Sample 1

Input

4 1
4 5 1 2
4 2
4 5 1 2
0 0

Output

17
2

Limitation

30s, 32768KiB for each test case.

Hint

附机翻题面

背景

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

问题描述

你需要编写一个程序来帮助劳伦斯找出如何最好地利用有限的资源。你有一些来自英国情报部门的信息。首先，轨道线是完全线性的——没有分支，没有热刺。接下来，英国情报部门对每个仓库都有一个战略重要性——从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