一道OJ上的算法题目
有N个排列好的数，不改变排列次序，要分成K个部分，每个部分至少有一个数， (其中K <=N)，若将每一个部分的数相乘，然后将K个部分相加，则可以得到一个表达式，求这个表达式的最大数值。
输入格式
文件第一行为2个整数N、K
下面N行为N个整数（N<=100，整数的范围都在整型以内）
样例输入
5 2
1
2
3
4
5
样例输出
121
我的思路是动态规划：以f[i][j]表示分成i组，最后一个数是j的最大数值。
以下是我的代码：
#include <iostream>
#include <algorithm>
using namespace std;
int n,a[101],m,f[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;
}
quifi
9 years, 10 months ago