TOPIC

TLE, ALGUÉM ME AJUDA AI ?

Ygor Ribeiro asked 2 years ago

#include<bits/stdc++.h>

using namespace std;

int memo[170][100000], valores[170], n, ans;

int pd(int pos, int soma){
    if(pos == n){
        return abs(soma - (ans-soma));
    }

    if(memo[pos][soma] != -1) return memo[pos][soma];

    int r1 = pd(pos+1,soma);
    int r2 = pd(pos+1,soma+valores[pos]);

    return memo[pos][soma] = min(r1,r2);

}

int main(){
    while(~scanf("%d",&n)){
        ans = 0;

        for(int i=0;i<n;i++) scanf("%d",&valores[i]), ans+=valores[i];

        memset(memo, -1, sizeof memo);

        printf("%d\n",pd(0,0));
    }

    return 0;
}

Remember not post solutions. Your post may be reviewed by our moderators.

  • Ygor Ribeiro replied 2 years ago

    Não consegui pensar em como fazer a PD iterativa, se puder me dar sugestão de algo para ler ou uma explicação, agradeço!

  • Luciano Ribeiro replied 2 years ago

    Tente fazer esta pd de forma iterativa. Deve passar..