最大连续和的最小值.txt

关于动态规划的poj的一些解题报告和代码

#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;

#define CISHUMAX 105
#define SHITOUMAX 100005
#define MAX 9999999
int f[SHITOUMAX][CISHUMAX];
int weight[SHITOUMAX];
//最大连续和的最小值 PKU 3273 Monthly Expense
//此题用动态规划会超时，但作为一种方法，不妨记录下来 
/*
输入:
8 3
1 2 3 4 5 6 7 8
*/

void cal(int num,int duan)
{
	int i,j,temp,max,k;
	for(i=1;i<=num;i++) 
		f[i][1]=f[i-1][1]+weight[i];
//	print(num,duan);
	for(j=2;j<=duan;j++)
	{	//分成j块
		for(i=j;i<=num;i++)
		{	//当前石头个数为i
			temp=MAX;
			for(k=1;k<i;k++)
			{	//k+1,...,i为新块数的石头
				if(f[i][1]-f[k][1]<f[k][j-1]) max=f[k][j-1];
				else max=f[i][1]-f[k][1];
				if(max<temp) temp=max;
			}
			f[i][j]=temp;
//			print(num,duan);
		}
	}
}


int main()
{
	int num,duan,i;
	scanf("%d%d",&num,&duan);
	for(i=1;i<=num;i++)
		scanf("%d",&weight[i]);
	cal(num,duan);
	cout<<f[num][duan]<<endl;
	return 0;
}