动态规划问题有N个正整数 分成k部分

求每一部分有最小和 加起来平方和也是最小和
输入 n k 9 4
1 2 3 4 5 6 7 8 9
输出 1 2 3 4 | 5 6 |7 8 |9

最小和 (1+2+3+4)^2+....9^2

恕我直言 我觉得最小和是
2 9| 5 6| 8 3| 1 4 7| = 507
你给的例子的结果是 527

而且求每一部分有最小和 我也看不懂 所以你还是把题目具体一点给出来

#include<iostream>
#include<math.h>
#define max 100
using namespace std;

bool tag[max];


void InitTag() {
    for(int i=0;i<max;i++) {
        tag[i]=false;
    }
}


int  Tag(int k,int low,int high,int *s) {
    if(k==1) {
        return -1;
    } else {
        int average=(s[high]-s[low])/k;
        for(int i=low+1;i<=high;i++) {
            if((s[i]-s[low])>average) {
                if(abs(s[i]-s[low]-average)>abs(s[i-1]-s[low]-average)) {
                    tag[i-1]=true;
                    return i-1;
                } else {
                    tag[i]=true;
                    return i;
                }
            }
        }
    }
}

void Delete(int *a,int *s) {
    delete []a;
    delete []s;
}

void Print(int *a,int n) {
    for(int i=0;i<n;i++) {
        cout<<a[i]<<" ";
        if(tag[i+1]==true) {
            cout<<"|";
        }
    }
}

void Print1(int *s,int n) {
    for(int i=0;i<=n;i++) {
        cout<<s[i]<<" ";
    }
}

int main() {
    int n,k;
    int *s,*a;
    cin>>n>>k;
    InitTag();
    a=new int[n];
    s=new int[n+1];
    s[0]=0;
    int p=0;
    int m;
    for(int i=0;i<n;i++) {
        cin>>a[i];
        p+=a[i];
        s[i+1]=p;
    }


    int q=Tag(k,0,n,s);
    int count=k-1;
    while(q!=-1) {
        q=Tag(count,q,n,s);
        count--;
    }
    Print(a,n);
    Delete(a,s);

    return 0;
}

/*
9 4
1 2 3 4 5 6 7 8 9
*/

图片说明

求大神指导 给个思路吧 要原地爆炸了

有人可以帮忙解答一下吗

dp[i][j]表示之前的j短平方和最小值

 #include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
int num[110] = {};
int dp[110][110] = {};
int flag[110][110] = {};
int sum[110][110] = {};
int main()
{
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n;++i){
        cin >> num[i];
    }
    for (int i = 0; i < n;++i){
        for (int j = i; j < n;++j){
            for (int k = i; k <= j;++k){
                sum[i][j] += num[k];
            }
        }
    }
    memset(dp, 0x6f, sizeof(dp));
    for (int i = 0; i < n;++i)
        dp[i][1] = sum[0][i] * sum[0][i];
    for (int i = 1; i < n; ++i)
    {
        for (int t = 2; t <= k; ++t)
        {
            dp[i][t] = dp[i - 1][t - 1] + num[i] * num[i];
            flag[i][t] = i - 1;
            for (int j = 0; j < i - 1; ++j)
            {
                if(dp[i][t]>dp[j][t-1]+sum[j+1][i]*sum[j+1][i]){
                    flag[i][t] = j;
                    dp[i][t] = dp[j][t - 1] + sum[j + 1][i] * sum[j + 1][i];
                }
                //dp[i][t] = min(dp[j][t - 1] + sum[j + 1][i] * sum[j + 1][i], dp[i][t]);
            }
        }
    }
    int t = k;
    int tag = flag[n - 1][k];
    vector<int> ans;
    while (t >= 1)
    {
        ans.push_back(tag); //cout << tag << " ";
        tag = flag[tag][--t];
    }
    for (int i = ans.size() - 1; i >= 0; --i)
    {
        if(i!=0){
            cout << "第" << k - i << "段和为";
            for(int j=ans[i];j<=ans[i-1];++j)
                cout << num[j] << " ";
            cout << endl;
        }
        else{
            cout << "第" << k - i << "段和为";
            for(int j=ans[i]+1;j<=n-1;++j)
                cout << num[j] << " ";
            cout << endl;
        }
        }
        cout << endl;
    cout << dp[n - 1][k] << endl;
}

dp[i][j]表示考虑前i个数字，分成j段的最小平方和，递推方程很容易想到，枚举倒数二段平方区间的末尾，然后取最小值。
图片说明

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
int num[110] = {};
int dp[110][110] = {};
int flag[110][110] = {};
int sum[110][110] = {};
int main()
{
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n;++i){
        cin >> num[i];
    }
    for (int i = 0; i < n;++i){
        for (int j = i; j < n;++j){
            for (int k = i; k <= j;++k){
                sum[i][j] += num[k];
            }
        }
    }
    memset(dp, 0x6f, sizeof(dp));
    for (int i = 0; i < n;++i)
        dp[i][1] = sum[0][i] * sum[0][i],flag[i][1]=-1 ;
    for (int i = 1; i < n; ++i)
    {
        for (int t = 2; t <= k; ++t)
        {
            dp[i][t] = dp[i - 1][t - 1] + num[i] * num[i];
            flag[i][t] = i - 1;
            for (int j = 0; j < i - 1; ++j)
            {
                if(dp[i][t]>dp[j][t-1]+sum[j+1][i]*sum[j+1][i]){
                    flag[i][t] = j;
                    dp[i][t] = dp[j][t - 1] + sum[j + 1][i] * sum[j + 1][i];
                }
                //dp[i][t] = min(dp[j][t - 1] + sum[j + 1][i] * sum[j + 1][i], dp[i][t]);
            }
        }
    }
    int t = k;
    int tag = flag[n - 1][k];
    vector<int> ans;
    while (t >= 1)
    {
        ans.push_back(tag); //cout << tag << " ";
        tag = flag[tag][--t];
    }
    for (int i = ans.size() - 1; i >= 0; --i)
    {
        if(i!=0){
            cout << "第" << k - i << "段和为";
            for(int j=ans[i]+1;j<=ans[i-1];++j)
                cout << num[j] << " ";
            cout << endl;
        }
        else{
            cout << "第" << k - i << "段和为";
            for(int j=ans[i]+1;j<=n-1;++j)
                cout << num[j] << " ";
            cout << endl;
        }
        }
        cout << endl;
    cout << dp[n - 1][k] << endl;
}

输出部分有点小问题，修改了。。。。。。
图片说明