¿Cómo se usa la programación dinámica para resolver la pregunta Problema TRT (Trato para las vacas) en Sphere Online Judge (SPOJ)?

Así que he estado atrapado en este problema desde el día que vi esta pregunta. Sabía sobre DP y cómo funciona, pero siempre le tengo mucho miedo y me molesta mucho abordarlos. Sabía que están relacionados con la recursión y resolver problemas a través de la recursión generalmente está bien, está bien para mí. Así que primero intenté pensar en un DP directamente pero no pude superarlo. Luego intenté crear el árbol de recursión y descubrir cosas desde allí. Pude ver que se repetían valores y puedo memorizarlos y crear un DP y resolver esto en el límite de tiempo, pero no pude entender cómo. Creé una recursión de fuerza bruta después e intenté pensar en modificarla, pero aún no obtuve resultados. Así que finalmente, después de días de alucinante, finalmente me encontré con esto hace unos minutos

La respuesta de Michal Danilák a ¿Hay buenos recursos o tutoriales para la programación dinámica (DP), además del tutorial de TopCoder?

y luego de unos minutos más me di cuenta de lo que había que hacer y luego estaba esa caja de color verde

Y aquí está la solución.

#include  #include  #include  using namespace std; int a[2000]; int max(int a,int b) { if(a>b) return a; return b; } int main() { int n; cin>>n; for(int i=0;i>a[i]; vector < vector  > dp(n+1,vector  (n+1,0)); for(int i=0;i<=n;i++) dp[i][0] = dp[0][i] = 0; for(int i=1;i<=n;i++) dp[i][i] = a[i-1]*n; for(int i=n-1;i>=1;i--) { for(int k = i,j = n;k>=1 && j>=1 ; j--,k--) { int y = n - (j-k+1) + 1; dp[k][j] = max( dp[k+1][j] + a[k-1]*y , dp[k][j-1] + a[j-1]*y ); } } cout< 

Y esta fue la solución de fuerza bruta que había probado antes

 #include  #include  using namespace std; int a[2000]; int max(int a,int b) { return a>b? a: b; } int get(int index,int low,int high,int day) { if(low>high+1) return 0; int ans = a[index]*day; int c1 = get(low,low+1,high,day+1); int c2 = get(high,low,high-1,day+1); return ans + max(c1,c2); } int main() { int n; scanf("%d",&n); for(int i=0;i 

Recomiendo encarecidamente que primero intente resolver este problema con recursividad. Una vez que lo haga, verá que la memorización es posible, y la implementación de dp será un poco más clara.

Mi solución de Python (algo cruda) de este problema:

  def calc (matriz, dp, días):
     c = 0
     tratar:
         para i en xrange (días-2, -1, -1):
             c + = 1
             para j en xrange (0, i + 1):
                 dp [i] .append (max ((i + 1) * array [j] + dp [i + 1] [j + 1], (i + 1) * array [j + c] + dp [i + 1 ] [j]))
     excepto Excepción, e:
         pasar
     devolver dp [0] [0]
    
 días = int (raw_input ())
 dp = []
 dp_array = []
 matriz = []
 para i en xrange (0, días):
	 item = int (raw_input ())
	 array.append (elemento)
	 dp.append ([])
	 dp_array.append (días * artículo)
 dp.pop ()
 dp.append (dp_array)
 imprimir calc (matriz, dp, días)