问题描述

一道OJ上的题，数的划分，求大神解答

有N个排列好的数，不改变排列次序，要分成K个部分，每个部分至少有一个数， (其中K <=N)，若将每一个部分的数相乘，然后将K个部分相加，则可以得到一个表达式，求这个表达式的最大数值。

输入格式
文件第一行为2个整数N、K
下面N行为N个整数（N<=100，整数的范围都在整型以内）
样例输入
5 2
1
2
3
4
5

样例输出
121

我的思路是动态规划：以f(ij)表示分成i组，最后一个数是j的最大数值。
以下是我的代码：

    #include <iostream>    #include <algorithm>    using namespace std;    int na[101]mf[101][101];    int main() {            cin>>n>>m;            for (int i=1;i<=n;++i)                    cin>>a[i];            for (int i=1;i<=m;++i)                    for (int j=i;j<=n;++j) {                            int s=1;                            for (int k=j-1;k>=i-1;--k) {                                    s*=a[k+1];                                    f[i][j]=max(f[i][j]f[i-1][k]+s);                            }                    }            cout<<f[m][n];            return 0;    }

解决方案

给一个死算的版本，供你校验结果，C#写的。

 using System;using System.Collections.Generic;using System.Linq;using System.Text;using System.Threading.Tasks;namespace ConsoleApplication1{    class Program    {        static void Main(string[] args)        {            int[] arr = { 1 2 3 4 5 };            var query = Split(arr 2);            int max = 0;            foreach (var item in query)            {                // Console.WriteLine(string.Join(""|"" item.Select(x => string.Join("" x))));                int r = item.Sum(x => x.Aggregate(1 (a b) => a * b));                if (max < r) max = r;            }            Console.WriteLine(max);        }        static IEnumerable<IEnumerable<IEnumerable<int>>> Split(IEnumerable<int> source int n)        {            int[] splitter = Enumerable.Range(1 n - 1).ToArray();            splitter[n - 2]--;            int[] lastsp = Enumerable.Range(source.Count() - n n -1).ToArray();            while (splitter.Zip(lastsp (x y) => x != y).Any(x => x == true))            {                for (int i = n - 2; i >= 0; i--)                {                    if (splitter[i] < lastsp[i])                    {                        splitter[i]++;                        for (int j = i + 1; j < n - 1; j++)                        {                            splitter[j] = splitter[i] + j - i;                        }                        break;                    }                }                IEnumerable<int>[] result = new IEnumerable<int>[n];                int acc = 0;                for (int i = 0; i < n; i++)                {                    if (i == n - 1)                    {                        result[i] = source.Skip(acc);                    }                    else                    {                        result[i] = source.Skip(acc).Take(splitter[i] - acc);                        acc = splitter[i];                    }                }                yield return result;            }        }    }}