poj2904--the mailbox manufrature problem.cpp

DP好题

#include<iostream>
using namespace std;
const int K=11;
const int N=110;
const int INF=1000000;

int max(int a,int b)
{
	return a>b?a:b;
}

int box,crack,cost[K][N][N];
int main()
{
	int t,i,j,wide,k,mid;
	int result,tmp1,tmp2;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d %d",&box,&crack);
		memset(cost,0,sizeof(cost));
		for(i=1;i<=crack;i++)
			for(j=i;j<=crack;j++)
				cost[1][i][j]=(i+j)*(j-i+1)/2;
			for(i=2;i<=box;i++)
				for(wide=1;wide<=crack;wide++)
					for(k=1;k+wide-1<=crack;k++)
					{
					/*if(wide==1)
					{
					cost[i][k][k]=k;
					continue;
					}*/
						cost[i][k][k+wide-1]=INF;				
						for(mid=k;mid<=k+wide-1;mid++)
						{
							tmp1=cost[i-1][k][mid-1];
							tmp2=cost[i][mid+1][k+wide-1];//这里的mid+1有可能会造成数组的越界
							result=max(tmp1,tmp2)+mid;
							if(result<cost[i][k][k+wide-1])
								cost[i][k][k+wide-1]=result;
						}
					}
					printf("%d\n",cost[box][1][crack]);
	}
	return 0;
}