Solução de Rogério Júnior
Clique aqui para ver o problema original
Se, para um determinado transporte, usei 
caminhões, o maior peso transportado foi 
e o valor do frete era 
, o preço será 
.
Abordaremos este problema usando programação dinâmica, pela simplicidade do código. O estado da DP será constituído de dois inteiros: 
e 
, e usaremos a função recursiva 
para calcular seu valor. Deste modo, a função 
deve retornar a resposta para a seguinte pergunta: dentre todas as possíveis maneiras de dividirmos os painéis solares a partir do índice entre caminhões, qual o peso do caminhão mais pesado na maneira de carregar os painéis em que o peso deste caminhão (mais pesado) é o menor possível?
A base da DP é muito simples: se só temos um caminhão (
), então ele transportará todos os painéis a partir do de índice , sendo portanto o mais pesado (por ser o único) e devemos retornar a soam de todos os painéis a partir do de índice .
Vejamos agora a fórmula geral da DP. se 
, vamos decidir que painéis colocaremos no primeiro caminhão. Para cada índice 
, veremos qual seria o peso do caminhão mais pesado se o primeiro caminhão levasse os painéis de a 
. Guardaremos em 
o peso que este primeiro caminhão está levando e a função 
retornará o peso do mais pesado entre os outros caminhões na configuração ótima. Assim, o peso do caminhão mais pesado (se o primeiro levar os painéis de a ) será o maior dentre e 
maior(i+1, qtd-1)
i
ini \leq i \leq n
e retornar o menor deles.
Agora que a função já está implementada, sabemos que o menor valor possível para o maior peso transportado pelos 
caminhões na tentativa de transportar os painéis de 1 a n é 
, logo devemos imprimir "
", onde é o valor do frete. Segue o código comentado para melhor entendimento.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #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; | |
| } |