2589 - 机器分配

总公司拥有高效设备M台，准备分给下属的N个分公司。各分公司若获得这些设备，可以为国家提供一定的盈利。问：如何分配这M台设备才能使国家得到的盈利最大？求出最大盈利值。其中M <= 15，N <= 10。分配原则：每个公司有权获得任意数目的设备，但总台数不超过设备数M。

Input

第1行有两个数，第一个数是分公司数N，第二个数是设备台数M。

接下来是一个N*M的矩阵，表明了第i个公司分配j台机器的盈利。

Output

第1行输出最大盈利值。

接下来N行，每行2个数，即分公司编号和该分公司获得设备台数。

Examples

Input

Output

Solution C

#include "stdio.h"
int n,m;
int a[11][16],b[11],f[11][16];
int main()
{
	int i,j,k;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
			scanf("%d",&a[i][j]);
	}
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			f[i][j]=f[i-1][j];
			for(k=1;k<=j;k++)
				if(f[i][j]<f[i-1][j-k]+a[i][k])
					f[i][j]=f[i-1][j-k]+a[i][k];
		}
	}
	printf("%d\n",f[n][m]);
	for(i=n;i>=1;i--)
	{
		for(j=m;j>=0;j--)
			if(f[i][m]==f[i-1][m-j]+a[i][j])
			{
				b[i]=j;
				m-=j;
				break;
			}
	}
	for(i=1;i<=n;i++)
		printf("%d %d\n",i,b[i]);
	return 0;
}

Solution C++

#include <iostream>
#include <cstdio>
#include <cstring>
#include <climits>

using namespace std;

int F[11][16];
int V[11][16];
int Ans=0,N,M;
void init(void);
void Work(void);
int Prim(int,int);

int main()
{	
	init();
	Work();
	
	return 0;
}

void init(void)
{
	memset(F,0,sizeof(F));
	memset(V,0,sizeof(V));
	
	int i,j;
	
	scanf("%d %d",&N,&M);
	
	for(i=1;i<=N;i++)
	{
		for(j=1;j<=M;j++)
		{
			scanf("%d",&V[i][j]);
		}
	}
}

void Work(void)
{
	int i,j,k;
	
	for(i=1;i<=N;i++)
	{
		for(j=1;j<=M;j++)
		{
			Ans=0;
			
			for(k=0;k<=j;k++)
			{
				if(F[i-1][k]+V[i][j-k]>Ans)
				{
					Ans=F[i-1][k]+V[i][j-k];
				}
			}
			
			F[i][j]=Ans;
		}
	}
	
	printf("%d\n",F[N][M]);
	
	Prim(N,M);
}

int Prim(int x,int y)
{
	int i,j;
	
	if(x==0) return 0;
	
	for(i=0;i<=y;i++)
	{
		if(Ans==F[x-1][i]+V[x][y-i])
		{
			Ans=F[x-1][i];
			Prim(x-1,i);
			printf("%d %d\n",x,y-i);
			break;
		}
	}
}

Time Limit	1 second
Memory Limit	128 MB

Discuss Stats

上一题下一题