所以感觉储存计算值还要另外用个数组保存~这样比较麻烦~九楼的做法直接每次循环计算值了当算了~虽然这样会影响效率~而且九楼的代码还没有考虑负数问题~那个跨遍历标记就是合并原来两个区间并把一个新的区间划分成原来两个区间~感觉这个要花点心思弄弄看~

当然~如果划分区间较小九楼的代码是可以的~但如果划分区间数量较多就出问题了~例如不能通过上面的那个案例~

谢大神耐心的回复！

我想分两段计算 就前面和后面比大小 可是不知道该怎么储存计算值和用哪一部分相比较
如果用三段for循环
minSun(s[n],group[k],n)
s[n]=s1...sn  //初始化输入
group[1]=s1[1] s2[1] ... s[i-1][1]  //n 分组
group[k] =s[i][k] s[i+1][k]...s[n][k]
min=-oo
for i=1 to n
for j=1to k
for t<i-1
    ss[i]=(s[t]+...+s[i])  //第一段和从s[t]加到s[i]
    q=min(q, ss[i]+minSum(ss,group[n-i][j],n-i))   //剩下的长为n-i，最大和sum[n-i] 在N里面从I 到L 位置最小和   
                                                                                          //这里有点懵不知道怎么写
for i=to k
    temp=group[1]^2+...+group[k]^2         // 可是这样感觉就全部遍历一遍了不太好
    best = min(temp,best)
 return best

n9  k4
1 2 3 4 5 6 7 8 9
1 2 3 4 | 5 6 | 7 | 8| 9 |
n5 k3
5 7 11 4 21
5 7 | 11 4 |21

这题我知道大概方法~但程序设计逻辑问题一时也弄不出来~储存计算数值如果用数组可以节约时间但要用数组来保存空间并时常更新数据~感觉比较麻烦~可以移动划分标记用划分的前后两段比较大小~但这个方法不完整的~

如果想完整解决就要涉及划分标记移动到任意位置问题~这样可能会把原来的划分空间合并并把一个新的空间划分为原来两块~计算比较麻烦~

理论上我想到算法这题可以优化~现在也说不清楚具体细节~就是知道这题有实现思路~但代码逻辑变量控制难度较大~所以我自己也说不清楚就不多说了~

还是想到点可以说的~具体就是要分两种情况讨论~第一种就是移动两个相邻区间中间的划分标记来比较~第二种情况就是把该划分标记跨越了相邻区间的划分标记到外面~把原来的两个相邻的区间合并了并把外面某个区间划分成新的两个子区间~

具体细节还是说不上来~知道自己有思路就先放下了~

谢谢帮主

我找到一个类似栗子
可是看不懂P语言

http://

打开网址看了一下~虽然可以由代码格式猜测其表达含义~但还是不能完全看懂~这题我有思路打算先放了~慢慢琢磨应该会有进展的~

解出来了~不过还没有优化(例如计算两段区间和可以用(K+1)*(K+1)的二维数组保存数据~这样每次读取数据就不用不断求和了)~

#include<stdio.h>
#include <limits.h>
#include<string.h>
#include<stdlib.h>
#include<conio.h>

void Init(int** s,int** p,int** p_min,int* N,int* K);    //初始化数据
void Print(int s[],int N);                               //输出数据
void Print_Result(int s[],int p_min[],int N);            //输出执行结果
int Count(int s[],int i,int j);                          //求和
int Sqrt_Sum(int s[],int p[],int K);                     //求平方和

int fun_Main1(int s[],int p[],int p_min[],int N,int K);
int fun_Main2(int s[],int p[],int p_min[],int N,int K,int min);

int fun_1(int s[],int p[],int N,int K,int sum);          //函数执行主体
int fun_2(int s[],int p[],int point,int r);
int fun_3(int s[],int p[],int point);       

void Reserve(int s[],int p_min[],int N,int K);            //数据倒置
void Swap(int*a ,int* b);                                 //交换函数

int main()
{
    int N=0;
    int K=0;

    int* s=NULL;
    int* p=NULL;
    int* p_min=NULL;

    int min=0;

    Init(&s,&p,&p_min,&N,&K);

    puts("测试输入数据如下:");
    Print(s,N);                //开始检查初始化数据

    min=fun_Main1(s,p,p_min,N,K);

    puts("划分结果如下:");
    Print_Result(s,p_min,N);

    printf("最小平方和为%d\n",min);

    free(s);
    free(p);
    free(p_min);

    return 0;
}

void Init(int** s,int** p,int** p_min,int* N,int* K)   //初始化数据
{
    int i=0;

    puts("请输入N K的值(中间用空格隔开):");
    scanf("%d%d",N,K);

    *s=(int*)malloc(*N*sizeof(int));
    *p=(int*)malloc((*K+1)*sizeof(int));
    *p_min=(int*)malloc((*K+1)*sizeof(int));

    if (*s==NULL||*p==NULL||*p_min==NULL)
    {
        puts("分配空间失败!");
        exit(0);
    }

    if (*N<=0||*K<=0||*N<*K)
    {
        puts("输入数据出错!");
        exit(0);
    }

    printf("请输入%d个数:\n",*N);
    for (i=0;i<*N;++i)
        scanf("%d",&((*s)[i]));

    for (i=0;i<*K;++i)
        (*p)[i]=i;

    (*p)[i]=*N;

    memmove(*p_min,*p,(*K+1)*sizeof(int));
}

int Count(int s[],int i,int j)      //求两个划分区间的和
{
    int sum=0;

    while (i<j)
        sum+=s[i++];

    return sum;
}

int Sqrt_Sum(int s[],int p[],int K)                //求平方和
{
    int i=0;
    int sum=0;

    for (i=0;i<K;i++)
    {
        int t=Count(s,p[i],p[i+1]);
        sum+=t*t;
    }

    return sum;
}

int fun_Main1(int s[],int p[],int p_min[],int N,int K)
{
    int min=INT_MAX;
    int min1=0;
    int min2=0;

    while (1)
    {
        min1=fun_Main2(s,p,p_min,N,K,min);

        Reserve(s,p_min,N,K);

        if (min1<min)
        {
            memmove(p,p_min,(K+1)*sizeof(int));
            min=min1;
        }

        min2=fun_Main2(s,p,p_min,N,K,min);

        Reserve(s,p_min,N,K);

        if (min2<min)
        {
            memmove(p,p_min,(K+1)*sizeof(int));
            min=min2;
        }

        if (min1==min2)
            break;
    }

    return min;
}

int fun_Main2(int s[],int p[],int p_min[],int N,int K,int min)
{
    int sum=0;
    int point=0;

    while (1)
    {
        point=K-1;
        sum=fun_1(s,p,N,K,sum); //sum为一个较优解  

        if (sum<min)
        {
            min=sum;

            memmove(p_min,p,(K+1)*sizeof(int));
        }

        while (point>0&&p[point+1]-p[point]==1)   //如果还没有完全遍历则需要继续比较
            --point;

        if (point==0)
            break;

        ++p[point];   //这里移动一个指针继续比较
    }

    return min;
}

int fun_1(int s[],int p[],int N,int K,int sum)   //函数执行主体
{
    int i=0;              //循环变量
    int point=0;       

    while (1)
    {
        point=K-1;   //每次重新遍历指针数据指向尾部

        while (point>0&&(!fun_3(s,p,point)||p[point+1]-p[point]==1))
        {
            --point;   

            for (i=point+1;i<K&&point!=0;++i)
                if (p[i+1]-p[i]>1&&fun_2(s,p,point,i))
                {
                    point=K-1;
                    break;
                }
        }

        if (point==0)
            break;


        while (p[point+1]-p[point]>1&&fun_3(s,p,point))
            ++p[point];
    }

    return Sqrt_Sum(s,p,K);

}

int fun_2(int s[],int p[],int point,int r)
{
    int t=p[r]+1;  //待划分数据的指针

    int a1=Count(s,p[point-1],p[point]);    //待定合并区间的左区间的值
    int a2=Count(s,p[point],p[point+1]);    //待定合并区间的右区间的值

    int b1=0;
    int b2=0;
    int b3=Count(s,p[r],p[r+1]);   

    int c1=a1*a2;
    int c2=0;

    for (;p[r+1]-t>1;++t)       //当划分区间长度大于1时
    {
        b1=Count(s,p[r],t);  //b1为新划分区间
        b2=Count(s,t,p[r+1]);
        c2=b1*b2;

        if (c1<c2)
        {
            int temp=p[point];

            while (point<r)   //对划分标记进行插入排序
            {
                p[point]=p[point+1];
                ++point;
            }
            p[point]=temp;

            return 1;    //如果划分标记有变动就要重新判断
        }
    }

    return 0;
}

int fun_3(int s[],int p[],int point)
{
    int a1=Count(s,p[point-1],p[point]);
    int a2=Count(s,p[point],p[point+1]);

    int b1=Count(s,p[point-1],p[point]+1);
    int b2=Count(s,p[point]+1,p[point+1]);

    return (a1*a1+a2*a2)>=(b1*b1+b2*b2);
}

void Reserve(int s[],int p_min[],int N,int K)                //数据倒置
{
    int i=0;
    int j=0;

    for (i=0,j=N-1;i<j;++i,--j)
        Swap(&s[i],&s[j]);

    for (i=1;i<K;++i)
        p_min[i]=N-p_min[i];

    for (i=1,j=K-1;i<j;++i,--j)
        Swap(&p_min[i],&p_min[j]);
}

void Swap(int*a ,int* b)                                 //交换函数
{
    *a^=*b;
    *b^=*a;
    *a^=*b;
}

void Print(int s[],int N)
{
    int i=0;

    for (i=0;i<N;++i)
        printf("%-4d",s[i]);

    puts("");
}

void Print_Result(int s[],int p_min[],int N)
{
    int i=0;
    int j=1;

    for (i=0;i<N;++i)
    {
        if (i==p_min[j])
        {
            printf("|  ");
            j++;
        }

        printf("%-4d",s[i]);
    }    

    puts("");
}

[此贴子已经被作者于2017-4-19 14:16编辑过]

解出来了~的确可以不用全组合遍历优化~规定遍历了K*(N-K)次~不过没对负数进行测试~感觉还可以完成对负数的测试和用二维数组保存两个区间的数据进行优化~

还得感谢azbcc版主代码教会久久用<limits.h>~感觉用INT_MAX作为基点比较可以方便一些~

[此贴子已经被作者于2017-4-19 08:16编辑过]

超级感谢版主大大提供
我在测试的时候发现了一丢丢丢的问题
下面是测试结果
请输入N K的值(中间用空格隔开):
17 10
请输入17个数:
15 3 18 3 21 7 14 2 17 9 20 2 38 4 35 6 23
测试输入数据如下:
15  3   18  3   21  7   14  2   17  9   20  2   38  4   35  6   23  
划分结果如下:
15  |  3   |  18  3   |  21  7   |  14  2   |  17  9   |  20  2   |  38  |  4   35  |  6   23  
最小平方和为6681
//6379

请输入N K的值(中间用空格隔开):
8 4
请输入8个数:
1 1 1 1 1 1 1 1
测试输入数据如下:
1   1   1   1   1   1   1   1   
划分结果如下:
1   |  1   1   |  1   1   |  1   1   1   
最小平方和为18
//应该是16

刚刚测试时也发现了~九楼的代码有些正确的但上面的却出问题了~还要改改看才行~