TOPIC

PROBLEM 1524 - URI Fórum 1.0

URI Online Judge asked 7 years ago

URI Online Judge Fórum 1.0

MOD

This topic was solved and cannot recieve new replies.

  • Felipe Derkian replied 4 years ago

    não entendi o problema.. alguém pode me dar uma luz? desde já agradeço

    MOD
  • 🧙The Install Wizard 🧙 replied 5 years ago

    Também é possível usar PD

  • Wilson Estécio Marcílio Júnior replied 6 years ago

    Pessoal, alguém me dá uma dica?? Pelo menos em qual paradigma devo me basear

  • Beto Jamaíca replied 5 years ago

    [quote="Guilherme Henrique"]Programei uma solução utilizando PD e acabei recebendo TLE, alguém pode me dizer o por quê?

    Resolvido. Acredito que com a solução top-down não é possível passar no tempo dado. Fiz guloso mesmo.
  • Beto Jamaíca replied 5 years ago

    Programei uma solução utilizando PD e acabei recebendo TLE, alguém pode me dizer o por quê? Segue o código:

    #include <bits/stdc++.h>
    #define inf 2147483600
    using namespace std;
    
    int n, lim, q[1005], dp[1005][1005];
    
    int func(int a, int k){
        if (k == lim && a >= n)
            return 0;
        if (k == lim || a >= n)
            return inf;
        if (dp[a][k] != -1)
            return dp[a][k];
        int ret = inf;
        for (int i = 0; a+i < n; i++){
            ret = min (ret, func(a+i+1, k+1) + (q[a+i]-q[a]));
        }
        return dp[a][k] = ret;
    }
    
    int main (void){
        q[0] = 0;
        while (scanf("%d%d", &n, &lim) != EOF){
            for (int i = 1; i < n; i++)
                scanf("%d", &q[i]);
            memset(dp,-1,sizeof dp);
            printf("%d\n", func(0,0));
        }
        return 0;
    }
  • Pedro Gabriel replied 5 years ago

    10% de W.A. ...

    Alguém me dá um suporte ? Fala apenas um caso de teste que não funciona ... =/ .

    #include <iostream>
    #include <cmath>
    
    using namespace std ;
    
    int main (){
        int *fila, tam, grupos, *dist, i, dd, de, dp, k = 0, sum=0;
        cin >> tam >> grupos ;
        fila = new int[tam] ;
        fila[0] = 0;
        dist = new int[grupos-1] ;
        for ( i=1; i<tam; i++ )
        {
            cin >> fila[i];
        }
    
        for ( i=0; i<tam - 1; i++ )
        {
            dp = abs(fila[i]-fila[i+1]);
            de = abs(fila[i-1] - fila[i]);
            dd = abs(fila[i+1] - fila[i+2]);
    
            if ( dp != de && dp != dd )
            {
                if ( k+1 < grupos )
                {
                    dist[k] = dp ;
                    k ++ ;
                }
            }
    
        }
    
        for (i=0; i<k; i++)
        {
            sum += dist[i];
        }
    
        cout << sum << endl ;
    
        return 0;
    }
  • Ramon de Oliveira replied 6 years ago

    É guloso.