City Flooding help

Aiuto
1

È da un po’ che sto provando a risolvere City flooding ma con scarsi risultati :smile:

Il codice che sono riuscito a scrivere per ora è questo

#include<iostream>
#include<fstream>
#include<algorithm>
using namespace std;
int const MAXN=100;
int l, n, k, fattoriale[MAXN], A[MAXN], fine, ris=0;
int solve(int indice, int somma, int usati)
{
   if(usati==k)
   {
   	if(somma>=l)
   		return 1;
   	return 0;
   }
   int r=0;
   for(int i=indice+1;i<fine;i++){
   	r+=solve(i, somma+A[i], usati+1);
   	r%=10007;
   }
   return r%10007;
}
int main()
{
   ifstream in("input.txt");
   ofstream out("output.txt");
   in>>l>>n>>k;
   fine=n-1;
   for(int i=0;i<fine;i++)		in>>A[i];
   sort(A, A+fine);
   reverse(A, A+fine);
   fattoriale[0]=1;
   fattoriale[1]=1;
   for(int i=2;i<n;i++)		fattoriale[i]=((fattoriale[i-1])%10007*i)%10007;
   if(k==fine)
   {
       int som=0;
       for(int i=0;i<fine;i++)
           som+=A[i];
      if(som>=l)   out<<fattoriale[fine];
      else         out<<0;
      return 0;
   }
   for(int i=0;i<fine-k+1;i++)	
   {
   	ris+=solve(i, A[i], 1);
   	ris%=10007;
   }
   int a=fattoriale[k]%10007, b=fattoriale[fine-k]%10007;
   out<<(ris*a*b)%10007;

}

Che ottiene 40/100 con un unico task errato nel terzo subtask(non capisco come :sweat:) ed il quarto subtask va quasi completamente in TLE

Quello che faccio con il mio codice è generare le combinazioni decrescenti lunghe k>=l una volta trovate queste combinazione che corrispondo ai k tombini che possono rimanere prima della casa del sindaco , la risposta sarà data da queste combinazioni* le loro permutazioni* le permutazione dei tombini dopo la casa del sindaco.

Devo trovare qualche modo per velocizzarlo (magari con la memoizzazione che ho provato a pensare a come sfruttarla ma onestamente non mi è venuto in mente nulla) e anche capire perché sbaglia quel task nel subtask 3.

Grazie mille in anticipo. :wink:

Fabio.

2

Si, la memoizzazione è la strada giusta, l’ho fatto molto tempo fa ma pensa un po’ a quando non hai più bisogno di fare calcoli (ne hai presi K) e alla struttura della tabella memo.

Questo è il mio codice:

#include <stdio.h>
#include <string.h>
#include <map>

using namespace std;

#define MOD  10007
#define MAXN 110
#define MAXL 1010

int L, K, N;
int V[MAXN];

int presi[MAXN];

int F(int n) {
    if (n == 0) return 1;
    int res = 1;
    for (int i = 1; i <= n; i++) {
        res *= i;
        res = res % MOD;
    }
    return res % MOD;
}


int memo[MAXN][MAXL][MAXN];

int dp(int i, int val, int took) {
    if (i >= N) return 0;
    val = max(0, val);

    if (took == K) {
        if (val <= 0) {
            return (F(took) * F(N-1-took)) % MOD;
        }
        return 0;
    }
    if (memo[i][val][took] != -1) return memo[i][val][took];

    int s1 = dp(i+1, val-V[i], took+1) % MOD;
    int s2 = dp(i+1, val, took) % MOD;

    memo[i][val][took] = (s1 + s2) % MOD;
    return memo[i][val][took];
}

int main() {
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

    scanf("%d", &L);
    scanf("%d%d", &N, &K);

    for (int i = 0; i < N - 1; i++) {
        scanf("%d", &V[i]);
    }

    memset(memo, -1, sizeof(int) * MAXN * MAXL * MAXN);

    printf("%d\n", dp(0, L, 0));

    return 0;
}
2 Mi Piace
3

Ok grazie mille, avevo pensato ad una memoizzazione di questo genere ma non credevo fosse cosi efficiente, in quanto alla fine non è così frequente che i parametri (i, val, took) siano identici perché se non ho capito male se io ho salvato questi valori vuol dire che ero già arrivato a questo indice con lo stesso valore quindi che devo raccogliere gli stessi litri d’acqua con lo stesso numero di tombini.

Comunque grazie mille lo stesso!! :slight_smile:

1 Mi Piace