最小m段和问题

[效云 李]

最小m段和问题
<<问题描述：
给定n 个整数组成的序列，现在要求将序列分割为m 段，每段子序列中的数在原序列
中连续排列。如何分割才能使这m段子序列的和的最大值达到最小？
<<编程任务：
给定n 个整数组成的序列,编程计算该序列的最优m 段分割，使m 段子序列的和的最大
值达到最小。
<<数据输入：
第1行中有2个正整数n和m。正整数n是序列
的长度；正整数m是分割的断数。
接下来的一行中有n个整数。
<<结果输出:
程序运行结束时，将计算结果输出。第1 行中的数是计算出
的m段子序列的和的最大值的最小值。
输入示例 输出示例
input
1 1
10

output
10

[效云 李]

这题我对题目理解有点问题，没大看懂，等你们做到这题，交流一下

[李效云]

// 动态规划-最小m段和问题.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include<iostream>
#include<fstream>
#include<vector>
using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
    int n=0,m=0;
    ifstream finput;
    finput.open("input.txt");
    finput>>n>>m;
   
    vector<int> a(n+1);
    int i=0;
    int temp=0;
    for(i=1;i<=n;++i)
    {
        finput>>temp;
        a[i]=temp;
    }
    finput.close();
   
    vector<vector<int> > b(m+1,vector<int>(n+1));
    //初始化
    for(i=1;i<=n;++i)
    {
        b[i][1]=b[i-1][1]+a[1];
    }
    void minsum(int,int,vector<int>,vector<vector<int> >&);
    void (*p_minsum)(int,int,vector<int>,vector<vector<int> >&);
    p_minsum=minsum;
    p_minsum(m,n,a,b);
   
    ofstream foutput;
    foutput.open("output.txt");
    foutput<<b[n][m];
    foutput.close();

    return 0;
}

void minsum(int m,int n,vector<int> a,vector<vector<int> >& b)
{
    int max(int,int);
    int i=0,j=0,k=0;
    int temp_max=0;
    int maxt;
    for(j=2;j<=m;++i)
        for(i=j;i<=n;++i)
        {
            for(k=1,temp_max=1000;k<i;++i)
            {
                maxt=max(b[i][1]-b[k][1],b[k][j-1]);
                if(temp_max>maxt)temp_max=maxt;
            }
            b[i][j]=temp_max;
        }
   
}

int max(int a,int b)
{
    if(a<b)return b;
    else return a;
}

2009/4/15 效云 李 <lixiao...@gmail.com>

[higer]

你速度真快啊！！！！

[李效云]

    for(j=2;j<=m;++j)
        for(i=j;i<=n;++i)
        {
            for(k=1,temp_max=1000;k<i;++k)

            {
                maxt=max(b[i][1]-b[k][1],b[k][j-1]);
                if(temp_max>maxt)temp_max=maxt;
            }
            b[i][j]=temp_max;
        }
   
}

int max(int a,int b)
{
    if(a<b)return b;
    else return a;
}

上次贴的代码有点问题，由于测试数据就一个当时没发现问题，后来看了一下，有两个地方循环控制错了，现在改一下

2009/4/15 higer <higerin...@gmail.com>

你速度真快啊！！！！

[higer]

这题目啥意思啊？