Transporte de Painéis Solares

paineis.cpp

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

#define MAXN 110
#define MAXC 15
#define INF 0x3f3f3f3f

// declaro as variáveis que vou usar
int n, c, f, casos, peso[MAXN], dp[MAXN][MAXC];

// função recursiva para calcular a DP
int maior(int ini, int qtd){
	
	// se já tiver calculado este estado,
	// retorno este resultado pré-calculado
	if(dp[ini][qtd]>=0) return dp[ini][qtd];
	
	// se qtd for 1, só tenho 1 caminhão
	if(qtd==1){
		
		// logo ele será o mais pesado
		// e devo retornar a soma de todos os painéis de ini a n
		// pois ele levará todos eles
		int soma=0;
		
		for(int i=ini; i<=n; i++) soma+=peso[i];
		
		return dp[ini][qtd]=soma;
	}
	
	// se tenho mais de um caminhão
	
	int soma=0, menor=INF;
	
	// peercorro todos os painéis
	// escolhendo qual será o último levado pelo primeiro caminhão
	for(int i=ini; i<=n; i++){
		
		// adiciono a soma seu valor
		soma+=peso[i];
		
		// e vejo se o peso do mais pesad é mínimo
		menor=min(menor,max(soma,maior(i+1, qtd-1)));
	}
	
	// retorno o melhor valor possível
	return dp[ini][qtd]=menor;
}

int main(){
	
	// leio a quantidade de casos
	scanf("%d", &casos);
	
	// para cada caso
	for(int t=1; t<=casos; t++){
		
		// zero a tabela de DP
		memset(dp,-1,sizeof(dp));
		
		// leio os valores da entrada
		scanf("%d %d %d", &n, &c, &f);
		
		for(int i=1; i<=n; i++) scanf("%d", &peso[i]);
		
		// e imprimo o resultado calculado pela DP
		printf("%d $%d\n", maior(1,c), maior(1,c)*c*f);
	}
	
	return 0;
}