【题解】搬书-C++

搬书

Description

陈老师桌上的书有三堆，每一堆都有厚厚的一叠，你想逗一下陈老师，于是你设计一个最累的方式给他，让他把书

拿下来给同学们。若告诉你这三堆分别有i,j,k本书，以及每堆从下到上书的质量，每次取书只能从任一堆的最上

面取，显然，每次取书陈老师的体力消耗都会加大，这里用体力系数代表，取下第一本书时，体力系数为1，第二

本书时体力系数为2，依次类推，而每次体力消耗值则为体力系数与书的重量之积。书最多有100本。

Input

第一行3个整数，分别为三堆书的数量i,j,k；第二行至第四行分别为每堆由下至上的书本重量。

Output

一行，输出最累方式的体力消耗总值

Sample Input

3 2 4

2 3 2

1 5

9 8 7 4

Sample Output

257

这道题我也实在想不出具体用的什么算法，就是三重循环跑一遍，时间复杂度O(i×j×k)，因为i,j,k的和才100，所以不会TLE。

代码就先贴在下面，自己理解一下【滑稽】。

#include<bits/stdc++.h>

using namespace std;

int a[101],b[101],c[101],f[101][101][101];

int I1,J1,K1,ans=0;

int book(int I,int J,int K)

{

	for(int i=0;i<=I;i++)

	{

		for(int j=0;j<=J;j++)

		{

			for(int k=0;k<=K;k++)

			{

				if(i>=1)f[i][j][k]=max(f[i][j][k],f[i-1][j][k]+a[i]*(i+k+j));

				if(j>=1)f[i][j][k]=max(f[i][j][k],f[i][j-1][k]+b[j]*(i+k+j));

				if(k>=1)f[i][j][k]=max(f[i][j][k],f[i][j][k-1]+c[k]*(i+k+j));

			}

		}

	}

	return f[I][J][K];

}

int main()

{

	cin>>I1>>J1>>K1;

	for(int i=I1;i>=1;i--)

		cin>>a[i];

	for(int i=J1;i>=1;i--)

		cin>>b[i];

	for(int i=K1;i>=1;i--)

		cin>>c[i];

	cout<<book(I1,J1,K1)<<endl;

	return 0;

}

ov.

巴特西

【题解】搬书-C++

最新文章

热门文章