Επεξηγήσεις για το πρόβλημα του γυμνασίου Β φάσης του 31ου ΠΔΠ
Πρόκειται για ένα απλό dp ώς αναφορά τον υπολογισμό των διαφορετικών συνδιασμών στην επιλογή του διαστήματος διακοπών.
Έστω ότι S είναι ο πίνακας Ν χαρακτήρων όπου κάθε χαρακτήρας είναι m ή s.
Κάνοντας το γράφημα της διαφοράς Σ(m) - Σ(s) ως προς την ημέρα i (i<=N), θα έχουμε N διαφορετικά σημεία.
Για λόγους προβολής θα τα παραστήσω με μια τεθλασμένη γραμμή στο διάγραμμα.
Το απλό σκεπτικό είναι να κάνουμε ένα O(N*N) για να βρούμε αν ανάμεσα στη μέρα i και στην αρχή των αξόνων υπήρχαν
άλλα ισοϋψή σημεία που ανάμεσα σε κάθε ένα από εκείνα τα σημεία και το i να υπάρχουν τόσα m όσα και s
και μετά να κάνουμε result = result + αριθμός_προηγούμενων_ισοϋψών_σημείων
Αυτό υποθέτω ήταν η αναμενόμενη λύση για γυμνάσιο.
Μπορούμε να το κάνουμε ποιο γρήγορο; Φυσικά.
Κρατάμε σε έναν πίνακα μεγέθους DPSIZE = 2*Ν. Πώς έγινε ο υπολογισμός του DPSIZE:
DPSIZE = |Σ(m)-Σ(s)| => -Ν <= Σ(m)-Σ(s) <= Ν
διότι αν έχουμε μόνο m, τότε Σ(m)==N ενώ αν έχουμε μόνο s, Τότε Σ(s)==N
Οπότε:
Κώδικας: Επιλογή όλων
//pdp31b-junior
#include <stdio.h>
#include <string.h>
int main(){
long long ans = 0;
int height = 0, N;
scanf("%d ",&N);//warning: προσέξτε το κενό μετά το %d που πετά όλα τα trailing white spaces
unsigned *_dp = new unsigned[2 * N + 1];
memset(_dp,0,sizeof(*_dp)*(2*N+1));
unsigned *dp = _dp + N; //ή ισοδύναμα unsigned *dp = &_dp[N];
//το dp[] είναι δείκτης στη μέση του _dp[] οπότε τις τιμές dp[i] μπορούμε να τις
//προσπελάσουμε με i από -N έως +Ν. Εναλλακτικά κάνουμε κάθε φορά _dp[i+N] για να μην βγούμε εκτός ορίων
dp[height] = 1; //αρχική κατάσταση: αριθμός m==0 και αριθμός s==0 υπάρχει 1 φορά στις 0 μέρες
for(int i=0;i<N;i++){
height += (getchar()=='m')? 1 : -1;
ans += dp[height];
dp[height]++;
//η πιό απλά για τις 2 πιο πάνω εντολές: ans += dp[height]++;
//η λίγο πιο καμμένα για τις 3 πιο πάνω εντολές: ans += dp[height += (getchar()=='m')? 1 : -1]++;;
}
printf("%llu\n",ans);
return 0;
}
Για το θέμα λυκείου, ήταν ένα απλό dp σαν το παραπάνω με ένα επιπλέον stack.
Η λύση δίνεται γραμμικά με ένα loop για το string.
Κρατάμε στο stack<int> μόνο τα ανοίγματα παρενθέσεων αποθηκεύοντας το i (τη θέση τους στο string
Κρατάμε σε ένα int dp[N] το πόσους συνδυασμούς έχουμε με ισορροπημένες παρενθέσεις που τελειώνουν στη θέση i
Κάθε φορά που συναντάμε ένα κλείσιμο παρένθεσης, ελέγχουμε το top στο stack και αν υπάρχει προσθέτουμε
και τους προηγούμενους συνδυασμούς
Κώδικας: Επιλογή όλων
/* USER: username
LANG: C++
TASK: cntbal */
#include <cstdio>
#include <stack>
using namespace std;
int main(){
FILE *in = fopen("cntbal.in","r"), *out = fopen("cntbal.out","w");
int n;
static long long dp0[1000003], *dp = dp0 + 1;
static char s[1000003];
while(fscanf(in,"%d %s",&n,s) == 2){
long long ans = 0;
memset(dp0,0,sizeof(dp0));
stack<int> S;
for(int i=0;s[i];i++){
if(s[i] == '('){
S.push(i);
} else if(S.size()){
dp[i] = dp[S.top()-1] + 1;
ans += dp[i];
S.pop();
}
}
fprintf(out,"%lld\n",ans);
}
return 0;
}