https://scut.online/p/299
\(dp[i][k]\) 为前 \(i\) 个数分 \(k\) 组的最大值, 那么 $dp[i][k]=max_{p=1}^{i-1}{dp[p][k-1]*sum(p+1,i)} $
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- struct BigInt {
- const static int mod = 10000;
- const static int DLEN = 4;
- vector<int> a;
- int len;
- BigInt() {
- a.resize(1);
- len = 1;
- }
- BigInt(int v) {
- a.resize(2);
- len = 0;
- do {
- a[len++] = v%mod;
- v /= mod;
- } while(v);
- }
- BigInt operator +(const BigInt &b)const {
- BigInt res;
- res.len = max(len,b.len);
- res.a.resize(res.len+1);
- for(int i = 0; i <= res.len; i++)
- res.a[i] = 0;
- for(int i = 0; i <res.len; i++) {
- res.a[i] += ((i < len)?a[i]:0)+((i < b.len)?b.a[i]:0);
- res.a[i+1] += res.a[i]/mod;
- res.a[i] %= mod;
- }
- if(res.a[res.len]> 0)
- res.len++;
- return res;
- }
- BigInt operator *(const BigInt &b)const {
- BigInt res;
- res.a.resize(len + b.len);
- for(int i = 0; i <len; i++) {
- int up = 0;
- for(int j = 0; j < b.len; j++) {
- int temp = a[i]*b.a[j] + res.a[i+j] + up;
- res.a[i+j] = temp%mod;
- up = temp/mod;
- }
- if(up != 0)
- res.a[i + b.len] = up;
- }
- res.len = len + b.len;
- while(res.a[res.len - 1] == 0 &&res.len> 1)
- res.len--;
- res.a.resize(res.len);
- return res;
- }
- bool operator>(const BigInt &b)const {
- if(len>b.len)
- return true;
- else if(len==b.len) {
- int ln=len-1;
- while(a[ln]==b.a[ln]&&ln>=0)
- ln--;
- if(ln>=0&&a[ln]>b.a[ln])
- return true;
- else
- return false;
- } else
- return false;
- }
- void output() {
- printf("%d",a[len-1]);
- for(int i = len-2; i>=0 ; i--)
- printf("%04d",a[i]);
- printf("\n");
- }
- };
- int a[205];
- BigInt dp[205][205];
- // 区间 [i,j] 分为 k 段取得的最大值
- inline int suma(int i,int j) {
- return a[j]-a[i-1];
- }
- int main() {
- #ifdef Yinku
- freopen("Yinku.in","r",stdin);
- #endif // Yinku
- int n,k;
- scanf("%d%d",&n,&k);
- for(int i=1; i<=n; i++) {
- scanf("%d",&a[i]);
- }
- for(int i=1; i<=n; i++) {
- a[i]+=a[i-1];
- }
- for(int i=1; i<=n; i++)
- dp[i][1]=BigInt(suma(1,i));
- for(int i=2; i<=n; i++) {
- int c=min(i,k);
- for(int ki=2; ki<=c; ki++) {
- for(int p=1; p<=i-1; p++) {
- BigInt t=dp[p][ki-1]*BigInt(suma(p+1,i));
- if(t>dp[i][ki])
- dp[i][ki]=t;
- }
- }
- }
- dp[n][k].output();
- }
来源: http://www.bubuko.com/infodetail-3092534.html