Compter est amusant Round.
Quatre problèmes de programmation dynamique. Un peu mystérieux.
Tous les problèmes étaient excellents. J'apprécie vraiment.
A.Compter est amusant 1
P2734 [IOI 1996 / USACO3.3] Jeu A.
Une astuce assez classique.
Descriptoin
Il y a une double file d'attente, les petits \(\delta\) et \(\mu\) peuvent chacun retirer un nombre d'une extrémité (petit \(\delta\) commence en premier), le score est la somme des nombres retirés, maintenant les deux veulent maximiser leur propre score, on demande si les deux adoptent la stratégie optimale, quelles sont les valeurs maximales des scores respectives.
Solution
Puisque c'est une double file d'attente, l'état qu'une personne fait face est toujours un intervalle de la séquence d'origine.
Ainsi, définissons deux tableaux \(dp\) pour représenter respectivement les valeurs maximales que les petits \(\delta\) et \(\mu\) peuvent obtenir en face de l'intervalle \([l,r]\).
La transition entre les deux tableaux se fait simplemnet.
Ensuite, vous calculez l'espace et découvrez qu'il n'est pas possible d'ouvrir deux tableaux \(dp\), mais vous remarquez cette constante \(\dfrac{1}{2}\), donc vous pouvez utiliser vector pour compresser.
Complexité \(O(n^2)\).
Code
#include <bits/stdc++.h> #define inf 0x3f3f3f3f #define infll 0x3f3f3f3f3f3f3f3fll using namespace std;
int n; int valeurs[5010],sommePrefixe[5010];
vector<vector > dp1,dp2;
int main(){ ios::sync_with_stdio(false); cin.tie(nullptr);
cin>>n;
for(int i=1;i<=n;i++) cin>>valeurs[i];
for(int i=1;i<=n;i++) sommePrefixe[i]=sommePrefixe[i-1]+valeurs[i];
dp1.resize(n+1);
for(int i=1;i<=n;i++) dp1[i].resize(n-i+1);
dp2.resize(n+1);
for(int i=1;i<=n;i++) dp2[i].resize(n-i+1);
for(int i=1;i<=n;i++) dp1[i][0]=dp2[i][0]=valeurs[i];
for(int longueur=2;longueur<=n;longueur++) for(int gauche=1,droite=longueur;droite<=n;gauche++,droite++){
dp2[gauche][droite-gauche]=max((sommePrefixe[droite]-sommePrefixe[gauche]-dp1[gauche+1][droite-(gauche+1)])+valeurs[gauche],(sommePrefixe[droite-1]-sommePrefixe[gauche-1]-dp1[gauche][droite-1-gauche])+valeurs[droite]);
dp1[gauche][droite-gauche]=max((sommePrefixe[droite]-sommePrefixe[gauche]-dp2[gauche+1][droite-(gauche+1)])+valeurs[gauche],(sommePrefixe[droite-1]-sommePrefixe[gauche-1]-dp2[gauche][droite-1-gauche])+valeurs[droite]);
}
cout<<dp1[1][n-1]<<" "<<sommePrefixe[n]-dp1[1][n-1]<<"\n";
return 0;
}
B.Compter est amusant 2
-------------------
P7335 \[JRKSJ R1\] XOR.
Ce qu'on appelle code de compétition volé pour obtenir la première place optimale.
### Description
> Vous avez une séquence, vous devez en sélectionner \\(k\\) intervalles disjoints \\(\[l\_i,r\_i\]\\), afin de maximiser \\(\\sum\\limits\_{i=1}^{k}\\operatorname{xor}\_{j=l\_i}^{r\_i}a\_j\\).
>
> **La séquence est générée aléatoirement.**
### Solution
Solution.
Considérons la programmation dynamique.
\\(dp\_{p,i}\\) représente la réponse en considérant les \\(i\\) premières positions divisées en \\(p\\) intervalles.
Comme on remarque que chaque transition n'a besoin que de la couche précédente, on peut compresser le tableau DP en une dimension et le répéter \\(k\\) fois.
L'approche naïve consiste pour chaque \\(i\\) à énumérer tous les \\(j\\) possibles, et à transférer \\(dp\_{i}\\gets\\max(dp\_{i},dplast\_{j-1}+\\operatorname{xor}\_{l=j}^{i}a\_l)\\).
Enfin, faites un préfixe \\(\\max\\) sur le tableau DP.
Maintenant, considérez les propriétés apportées par les données aléatoires.
Considérons un point vers la gauche, quels points de décision sont possibles.
À partir de ce point vers la gauche, faites une somme suffixe XOR, alors tous les points de décision possibles sont les positions de chaque maximum suffixe de la somme suffixe. Parce que les positions non maximales du suffixe seront dominées par les positions maximales du suffixe à droite.
Pour chaque \\(i\\), le nombre attendu de ces points de décision devrait être \\(O(\\log V)\\). Ceci est équivalent au nombre de maximums de préfixe dans une séquence aléatoire.
Traitez ces informations, et à chaque fois transférez violemment, exécutez le DP \\(k\\) fois, et c'est terminé.
La complexité attendue devrait être \\(O(nk\\log V)\\).
### Code
#include <bits/stdc++.h> #define inf 0x3f3f3f3f #define infll 0x3f3f3f3f3f3f3f3fll using namespace std;
int n,k; int tableau[3010],somme[3010];
vector suffixes[3010];
long long dp[3010],precedent[3010];
void resoudre(){ memcpy(precedent,dp,(n+1)*sizeof(long long)); memset(dp,0,(n+1)*sizeof(long long)); for(int i=1;i<=n;i++) for(int x:suffixes[i]) dp[i]=max(dp[i],precedent[x-1]+(somme[i]^somme[x-1])); for(int i=1;i<=n;i++) dp[i]=max(dp[i],dp[i-1]); }
int main(){ ios::sync_with_stdio(false); cin.tie(nullptr);
cin>>n>>k;
for(int i=1;i<=n;i++) cin>>tableau[i];
for(int i=1;i<=n;i++) somme[i]=somme[i-1]^tableau[i];
for(int i=1;i<=n;i++){
int xorActuel=0,maxXor=-1;
for(int p=i;p>=1;p--){
xorActuel^=tableau[p];
if(xorActuel>maxXor) suffixes[i].push_back(p),maxXor=xorActuel;
}
}
while(k--) resoudre();
cout<<dp[n]<<"\n";
return 0;
}
C.Compter est amusant 3
-------------------
P10547 \[THUPC 2024 Finale\] Jeu de permutations.
Les deux conditions prises séparément je sais les compter mais ensemble je ne sais pas pourquoi.
Un pur comptage très éducatif.
### Description
> Vous avez une permutation \\(p\\), initialement \\(p\_i=i\\).
>
> Le petit \\(\\delta\\) effectuera exactement \\(n\\) opérations, échangeant à chaque fois deux positions **différentes** de \\(p\\).
>
> Le petit \\(\\mu\\) peut échanger \\(p\_i,p\_j\\) en temps \\(|i-j|\\), maintenant on vous demande combien de permutations obtenues après les opérations du petit \\(\\delta\\) permettent au petit \\(\\mu\\) de revenir à l'état initial en **temps** au plus \\(m\\).
>
> Réponse modulo \\(10^9+7\\).
### Solution
Ce que vous ne comprenez pas peut consulter cette excellente solution.
Caractérisons les deux conditions.
Le temps minimum pour revenir à la permutation initiale en échangeant \\(p\_i,p\_j\\) en temps \\(|i-j|\\) est \\(\\frac{1}{2} \\sum\_{i=1}^{n}|i-p\_i|\\).
Développons chaque terme sur chaque intervalle \\(\[k,k+1\]\\), c'est une transformation classique.
\\(n\\) échanges de deux positions **différentes** de \\(p\\), considérons les cycles de permutation, chaque échange changera évidemment la parité du nombre de cycles, après \\(n\\) opérations le nombre de cycles est évidemment pair.
Considérons la permutation comme \\(n\\) arêtes orientées \\(i\\to p\_i\\), ajoutons chaque \\(p\_w\\) dans l'ordre croissant.
Soit \\(dp\_{i,j,k,0/1}\\) le fait que nous ayons considéré l'arête \\(p\_w=i\\), il y a actuellement \\(j\\) chaînes, la contribution à la première restriction est \\(k\\), et la parité du nombre de cycles de permutation est \\(0/1\\).
Transférons en énumérant comment cette arête peut s'associer aux chaînes précédentes : ajouter une nouvelle chaîne, former un cycle, s'attacher aux deux extrémités d'une chaîne existante, fusionner deux chaînes, transformer une chaîne en cycle.
Soit \\(k'=k+j\\), c'est-à-dire la forme de contribution à la première restriction.
- Ajouter une nouvelle chaîne, \\(dp\_{i,j+1,k',x} \\gets dp\_{i,j+1,k',x}+dp\_{i-1,j,k,x}\\).
- Former un cycle, \\(dp\_{i,j,k',1-x} \\gets dp\_{i,j,k',1-x}+dp\_{i-1,j,k,x}\\).
- S'attacher aux deux extrémités d'une chaîne existante, \\(dp\_{i,j,k',x} \\gets dp\_{i,j,k',x}+2\\times j \\times dp\_{i-1,j,k,x}\\).
- Fusionner deux chaînes, \\(dp\_{i,j-1,k',x} \\gets dp\_{i,j-1,k',x}+j \\times (j-1) \\times dp\_{i-1,j,k,x}\\).
- Transformer une chaîne en cycle, \\(dp\_{i,j-1,k',1-x} \\gets dp\_{i,j-1,k',1-x}+j \\times dp\_{i-1,j,k,x}\\).
Initialisation \\(dp\_{0,0,0,0}=1\\), la réponse est \\(\\sum\_{k=0}^m dp\_{n,0,k,0}\\).
La deuxième dimension augmentera de \\(j\\) à chaque fois, il suffit d'ouvrir la limite jusqu'à \\(O(\\sqrt m)\\). C'est aussi une optimisation courante.
Nécessite un tableau roulant et des requêtes hors ligne.
Complexité \\(O(nm\\sqrt m)\\).
### Code
#include <bits/stdc++.h> #define inf 0x3f3f3f3f #define infll 0x3f3f3f3f3f3f3f3fll using namespace std;
static const unsigned long long mod=1e9+7; class modint{ // ... };
int q; vector<pair<int,int> > requetes[510];
int n,m; modint dp[2][80][5010][2];
const int S=75; modint Reponses[1010];
int main(){ ios::sync_with_stdio(false); cin.tie(nullptr);
cin>>q;
for(int i=1;i<=q;i++){
cin>>n>>m;
requetes[n].push_back({m,i});
}
n=500,m=5000;
dp[0][0][0][0]=1;
for(int wi=1,i=1;wi<=n;wi++,i^=1){
memset(dp[i],0,sizeof dp[i]);
for(int j=0;j<=min(wi,S);j++){
for(int k=0,nk=j;nk<=m;k++,nk++){
for(int x:{0,1}){
modint valeur=dp[i^1][j][k][x];
if(valeur==0) continue;
if(j+1<=S) dp[i][j+1][nk][x]+=valeur;
dp[i][j][nk][x^1]+=valeur;
dp[i][j][nk][x]+=valeur*2*j;
if(j) dp[i][j-1][nk][x^1]+=valeur*j;
if(j) dp[i][j-1][nk][x]+=valeur*j*(j-1);
}
}
}
for(auto [qm,id]:requetes[wi]) for(int k=0;k<=qm;k++) Reponses[id]+=dp[i][0][k][0];
}
for(int i=1;i<=q;i++) cout<<Reopnses[i]<<"\n";
return 0;
}
D.Compter est amusant 4
-------------------
P9047 \[PA 2021\] Collecteurs d'impôts.
Un bon problème.
### Description
> Vous avez un arbre, vous pouvez sélectionner plusieurs chaînes de longueur \\(4\\) **sans arêtes communes** (nombre d'arêtes), la valeur sélectionnée est la somme des poids de toutes les arêtes dans l'union de ces chaînes.
>
> Vous devez maximiser la valeur sélectionnée.
### Solution
Il n'est pas difficile de penser à une programmation dynamique sur arbre.
Soit l'état \\(dp\_{x,0/1/2/3}\\) représente la réponse maximale pour le sous-arbre ayant \\(x\\) comme racine, avec une chaîne de longueur \\(0/1/2/3\\) s'étendant vers le haut à partir de \\(x\\).
La transition considère tous les sous-arbres d'un point, et il faut les apparier deux par deux : \\(0\\) et \\(2\\) sont appariés, \\(1\\) et \\(1\\) sont appariés, \\(3\\) contribue seul à la réponse, et on choisit un sous-arbre de chaîne, en ajoutant une arête pour essayer de contribuer aux quatre états.
C'est similaire à un problème à sacs à dos par groupes, où chaque fils ne peut choisir qu'un état pour contribuer.
Mais ce problème à sacs àdos a une propriété, le poids des articles est \\(1\\) (\\(dp\_{y,0}\\)), \\(0\\) (\\(dp\_{y,1/3}\\)) ou \\(-1\\) (\\(dp\_{y,2}\\)).
Considérons un tableau temporaire de sacs à dos \\(f\_{i,0/1}\\) représentant la somme des poids actuelle du sac est \\(i\\), c'est-à-dire la différence entre le nombre de \\(dp\_{y,0}\\) sélectionnés et le nombre de \\(dp\_{y,2}\\) sélectionnés, et qu'un nombre impair ou pair de \\(0\\) (\\(dp\_{y,1}\\)) est sélectionné, la réponse maximale.
Finalement, on a :
\[\begin{cases} dp_{x,0}=f_{0,0}\\ dp_{x,1}=f_{1,0}\\ dp_{x,2}=f_{0,1}\\ dp_{x,3}=f_{-1,0} \end{cases} \]Mais le calcul de ce sac à dos est \\(O(n)\\).
Considérons la forme des solutions finales valides, les décisions sont de la forme d'une séquence composée uniquement de \\(-1\\), \\(0\\), \\(1\\).
Dans le pire des cas, la somme des poids correspondant à ces décisions atteindra \\(O(n)\\).
Cependant, nous avons une conclusion classique : pour une séquence de longueur \\(n\\), avec seulement \\(-1\\), \\(1\\) et somme de tous les éléments \\(0\\) ou proche de \\(0\\), si on la mélange aléatoirement, la valeur maximale absolue des sommes préfixes est de l'ordre de \\(O(\\sqrt n)\\).
La conclusion pour une séquence composée de \\(-1\\), \\(0\\), \\(1\\) est évidemment pas plus faible que la conclusion ci-dessus.
Ainsi, avant la transition, nous mélangeons aléatoirement tous les fils, et la limite supérieure de la capacité du sac à dos ouverte à \\(O(\\sqrt n)\\) suffit.
### Code
#include <bits/stdc++.h> #define inf 0x3f3f3f3f #define infll 0x3f3f3f3f3f3f3f3fll using namespace std;
mt19937 generateur((unsigned int)chrono::high_resolution_clock::now().time_since_epoch().count()); long long aleatoire(long long l,long long r){return generateur()%(r-l+1)+l;}
struct Graphe{ struct arete{int vers,suivant;long long poids;}aretes[400010]; int tete[200010],compteArete=1;
inline void ajouterArete(int x,int y,long long poids){aretes[compteArete]={y,tete[x],poids},tete[x]=compteArete++;}
vector<pair<int,long long> > operator[](int x){
vector<pair<int,long long> > resultat;
for(int i=tete[x];i;i=aretes[i].suivant) resultat.push_back({aretes[i].vers,aretes[i].poids});
return resultat;
}
}graphe;
int n; long long dp[200010][4];
const int P=471; long long temp[470<<1|1][2],temp2[470<<1|1][2];
void dfs(int intNoeud,int parent=0){ vector<pair<int,long long> > voisins=graphe[intNoeud]; for(auto [fils,poids]:voisins) if(fils!=parent) dfs(fils,intNoeud);
shuffle(voisins.begin(),voisins.end(),generateur);
memset(temp,-0x3f,sizeof temp);
temp[P][0]=0;
for(auto [fils,poids]:voisins) if(fils!=parent){
memset(temp2,-0x3f,sizeof temp2);
for(int i=-450;i<=450;i++){
for(int z:{0,1}){
temp2[i+P][z]=max(temp2[i+P][z],temp[i+P][z]+dp[fils][0]);
if(i+1<=450) temp2[i+1+P][z]=max(temp2[i+1+P][z],temp[i+P][z]+dp[fils][0]+poids);
temp2[i+P][z^1]=max(temp2[i+P][z^1],temp[i+P][z]+dp[fils][1]+poids);
if(i-1>=-450) temp2[i-1+P][z]=max(temp2[i-1+P][z],temp[i+P][z]+dp[fils][2]+poids);
temp2[i+P][z]=max(temp2[i+P][z],temp[i+P][z]+dp[fils][3]+poids);
}
}
memcpy(temp,temp2,sizeof temp);
}
dp[intNoeud][0]=max(0ll,temp[P][0]);
dp[intNoeud][1]=temp[P+1][0];
dp[intNoeud][2]=temp[P][1];
dp[intNoeud][3]=temp[P-1][0];
}
int main(){ ios::sync_with_stdio(false); cin.tie(nullptr);
cin>>n;
for(int i=1;i<n;i++){
int x,y,poids;cin>>x>>y>>poids;
graphe.ajouterArete(x,y,poids),graphe.ajouterArete(y,x,poids);
}
dfs(1);
cout<<dp[1][0]<<"\n";
return 0;
}