2024-07-12
한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina
Après avoir lu la question, vous savez que dans une chaîne de longueur n, trouvez la longueur de la sous-chaîne palindrome la plus longue. Une sous-chaîne palindrome peut être comprise comme une chaîne symétrique. En raison de la symétrie, l'idée de base est la "méthode d'expansion centrale", c'est-à-dire que la chaîne est parcourue en séquence, puis étendue aux deux côtés du caractère. Si les caractères des deux côtés sont égaux, alors c'est le cas. enregistré dans la variable retlen. Après le parcours, nous obtenons finalement Just return the maximum length. Pour faciliter la compréhension, faites un dessin :
De plus, lors de l’analyse de l’exemple, nous devons également prêter attention à la différence entre les nombres impairs et pairs, la prochaine étape est donc la mise en œuvre du programme.
Premièrement, selon la « méthode d'expansion centrale » de l'analyse des idées, la chaîne est parcourue et développée à partir de la station centrale en i. Le retlen obtenu à son tour est continuellement comparé et mis à jour avec retlen Ensuite, car il est nécessaire de faire la distinction entre les impairs. nombres et nombres pairs, respectivement Trouvez la valeur maximale et enfin comparez-la pour obtenir le retlen maximum final et renvoyez-le.
class Solution
{
public:
int getLongestPalindrome(string A)
{
size_t len = A.size();
int left = 0;
int right = 0;
int retlen = 0;
//偶数
for(int i = 0;i < len; i++)
{
left = i;
right = i + 1;
while(left >= 0 && right < len && A[left] == A[right])
{
left--;
right++;
}
retlen = max(retlen ,right - left - 1);
}
//奇数
for(int j = 0;j < len;j++)
{
left = j;
right = j;
while(left >= 0 && right < len && A[left] == A[right])
{
left--;
right++;
}
retlen = max(retlen ,right - left - 1);
}
return retlen ;
}
};
Après avoir lu la question, vous savez que pour le mécanisme d'achat et de vente d'un groupe d'actions, vous ne pouvez acheter et vendre qu'une seule fois. Trouvons le profit maximum obtenu si vous perdez de l'argent, peu importe le moment où vous achetez ou vendez, peu importe comment. beaucoup vous perdez, c'est-à-dire qu'il n'y a pas de profit, alors sortie 0 C'est tout. Ensuite, l'idée de base est d'énumérer/méthode de force brute, de trouver la différence de profit de chaque groupe et de renvoyer la valeur maximale. Après l'avoir essayé, il s'avère que la méthode à deux couches expirera et ce problème se limite à. 1 ms pour résoudre. Par conséquent, il est nécessaire d'optimiser sur la base de la méthode de la force brute, donc la méthode de la force brute est également écrite. Ensuite, sur la base de la méthode de la force brute, le retour en arrière a été répété trop de fois, l'optimisation, la réflexion et la découverte, si nous y réfléchissons. inverser, pensez d'abord à vendre. Ensuite, il vous suffit de trouver la valeur minimale avant le point de vente, et la différence obtenue est la différence maximale, ce qui signifie que vous ne devez la parcourir qu'une seule fois. La prochaine étape est la mise en œuvre du programme.
Premièrement, selon l'analyse de la méthode de force brute, toutes les situations sont énumérées afin de trouver la différence maximale. Cette question expirera. Il faut donc l'optimiser.
#include <iostream>
using namespace std;
const int N = 1e5 +10;
int arr[N];
int main()
{
int n;
cin >> n;
for(int i = 0;i < n;i++)
cin >> arr[i];
int maxval = 0;
for(int i = 0;i < n; i++)
{
for(int j = i;j < n;j++)
{
maxval = max(maxval , arr[j]- arr[i]);
}
}
cout << maxval << endl;
return 0;
}
Sur la base de la méthode de force brute ci-dessus, une optimisation est effectuée Afin de bien la comprendre, un diagramme de démonstration est dessiné sur la base de l'analyse de l'idée :
Ensuite, pour implémenter le programme, écrivez l'entrée selon les besoins, puis définissez minval pour initialiser arr[0] comme valeur minimale supposée pour la comparaison et la mise à jour du parcours, puis définissez un maxSub pour représenter la différence maximale par rapport à minval lors du passage à la position i. , ce qui vaut la peine Notez que lors du parcours, faites attention à l'ordre de minval et maxSub, recherchez d'abord la valeur minimale minval, puis recherchez maxSub.
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n = 0;
cin >> n;
vector<int> arr(n);
int m = 0;
while(n--)
{
cin >> arr[m];
m++;
}
int minval = arr[0];
int submax = 0;
for(int i = 0;i<arr.size();i++)
{
minval = min(arr[i],minval);
submax = max(submax, arr[i] - minval);
}
cout << submax << endl;
return 0;
}
Après avoir lu la question, vous saurez combien de chemins il y a au maximum pour aller d'un point A à un point B selon certaines règles. Lors de l'analyse de la question, vous devez savoir que selon certaines règles, vous pouvez aller vers la droite ou vers le bas, ce qui évoque l'idée de programmation dynamique dp. Ce à quoi vous devez également faire attention dans la question, c'est le point de contrôle. du cheval ne peut pas être déplacé (visité), c'est-à-dire le chevalier aux échecs. Les points dessinés par la diagonale "soleil" sur les coordonnées, y compris le point de départ du cheval, sont appelés points de contrôle. Parmi eux, le cheval est un point fixe (x, y) donné au début, et la question donne aussi la relation entre le point de saut du cheval et le point de départ du cheval. De plus, il est à noter que selon l'exemple et l'échiquier, la taille de l'échiquier est de (n+1)(m+1)。
Ainsi, sur la base de l’analyse ci-dessus, nous pouvons conclure que :
(1) Vous pouvez utiliser des idées de programmation dynamique pour résoudre des problèmes ;
(2) Le point de contrôle du cheval, en plus du « soleil » diagonal, comprend également sa propre position de départ ;
(3). La taille de l'échiquier est (n+1)(m+1).
Par conséquent, après avoir analysé les points d'attention, nous revenons à la représentation d'état dp et à l'équation de transition d'état de la programmation dynamique ;
Sur la base des règles de marche du sujet, l'état dp[i][j] est défini pour représenter : il existe au plus plusieurs chemins vers cette position ;
Dérivez l'équation de transition d'état : dp[i][j] = d[i][j-1] + d[i-1][j] ;
De plus, notez que si la position de départ du point B coïncide avec la position de départ du cheval ou le point de contrôle, et que le haut et la gauche du point B sont tous bloqués, c'est-à-dire le point de contrôle, alors dans le cas extrême ci-dessus , à ce moment dp[i] [j] = 0; Ensuite, l'étape suivante est la mise en œuvre du programme.
Tout d'abord, écrivez l'entrée en fonction de l'analyse de l'idée, définissez et ouvrez le tableau dp (deux pièges seront abordés plus tard), et en fonction de la taille de l'échiquier, afin de pouvoir décrire les coordonnées de manière uniforme, un supplément la ligne et la colonne seront ouvertes ici, puis x et y doivent être mappés. Définissez simplement les coordonnées +=1, puis explorez le problème d'initialisation de dp et dessinez une image pour la rendre plus claire :
Ensuite, le tableau bidimensionnel réel est parcouru de [1, n+1] et [1, m+1], jugeant constamment le traitement des situations extrêmes, et produisant finalement dp[n+1][m+1]. À ce stade, l’idée ne pose aucun problème. Les étapes récapitulatives sont les suivantes :
(1), cartographier les coordonnées de x et y ;
(2) Initialisez dp[0][1] = 1 ou dp[1][0] = 1 selon la définition du tableau (ouvrez un calque supplémentaire) ;
(3) Parcourez le tableau à deux chiffres, en faisant attention au parcours de contrôle des limites de [1, n+1] et [1, m+1] ;
a. Déterminer les situations extrêmes : 1. Le point de contrôle du cheval bloque le chemin 2. Problème de coïncidence ;
b. Équation de transition d'état d'exécution normale : dp[i][j] = d[i][j-1] + d[i-1][j] ;
(4), enfin, sortie dp[n+1][m+1].
De plus, les deux pièges mentionnés ci-dessus sont qu'après avoir fini d'écrire, la soumission a échoué et j'ai constaté que les données étaient hors de portée, il est donc préférable d'utiliser long long pour ouvrir le tableau. Un autre piège est la plage de taille de. l'ouverture est trop grande Le premier étage est utilisé, il doit donc être au moins supérieur ou égal à 22. Auparavant, l'utilisation de dp[21][21] ne pouvait pas répondre à tous les cas d'utilisation.
#include <iostream>
using namespace std;
long long dp[22][22];
int main()
{
int n,m,x,y;
cin >> n >> m >> x >> y;
//映射坐标
x += 1;
y += 1;
//初始化
dp[0][1] = 1;
//遍历
for(int i = 1;i <= n+1; i++)
{
for(int j = 1;j <= m+1; j++)
{
//极端情况的处理: 1.马控制点 2.自身重合
if((i != x && j != y && abs(i - x) + abs(j - y) == 3) || (i == x && j == y))
{
dp[i][j] = 0;
}
else
{
dp[i][j] = dp[i][j-1] + dp[i-1][j];
}
}
}
cout << dp[n+1][m+1] << endl;
return 0;
}
sous-chaîne palindrome la plus longue
Le meilleur moment pour acheter et vendre des actions (1)
[Groupe de vulgarisation NOIP2002] Traverser le pion de la rivière
Il se consacre à la recherche technologique depuis plus de trente ans, maîtrise divers langages tels que java, linux, javascript, php, css, etc., et a apporté de nombreuses contributions dans le domaine de l'open source. une station de documentation pour les développeurs pour partager certains problèmes de développement technologique pour référence future.
