整理图书

描述

小明是图书鹳狸猿，他有很多很多的书堆在了一起摆在了架子上，每摞书是横着放的，而且每摞书是订好的

是一个整体，不可分开，（可以想象架子是一条直线）,但是这些书高度却参差不齐，小明有强迫症，看不得不整齐

所以他想让这些书的高度形成一个非降序列他才舒心，可是这些书是有序的，所以他只能把其中的一摞书和他相邻的书装订在一起

形成一摞新的书，那么他最少的装订次数是多少呢

输入

多组测试数据，处理到文件结束
每组数据开始有一个n(1<=n<=1000)表示有n摞书
接下来一行是这n摞书的高度a[i]，(1<=a<=10^5)(虽然这个高度有点扯淡)

输出

首先输出Case num : 表示第几组数据
接下来对于每组数据输出最少的装订次数

样例输入

5 8 2 7 3 1 1 100

样例输出

Case 1: 3 Case 2: 0

提示

第一组样例:将后4本书装订在一起，共装订3次，组成8 13
第二组样例:只有一本书，无需装订

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define N 5010
#define INF 0x3f3f3f3f
using namespace std;
int a[N];
int sum[N];
int dp[N];
int b[N];
int main()
{
	int n,T=1;
	int i,j;
	while(scanf("%d",&n)!=EOF)
	{
		memset(sum,0,sizeof(sum));
		for(i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
			b[i]=max(b[i-1],a[i]);
			sum[i]=sum[i-1]+a[i];
		}
		memset(dp,INF,sizeof(dp));
		dp[0]=dp[1]=0;
		for(i=2;i<=n;i++)
		{
			for(j=i-1;j>=0;j--)
			{
				if(b[j]<=sum[i]-sum[j])
				{
					if(dp[i]>dp[j]+i-j-1)
					{
						dp[i]=dp[j]+i-j-1;
						b[i]=sum[i]-sum[j];
						break;
					}
				}
			}
		}
		printf("Case %d: %d\n",T++,dp[n]);
	}
	return 0;
}