2024-07-12
한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina
Nachdem Sie die Frage gelesen haben, wissen Sie, dass Sie in einer Zeichenfolge der Länge n die Länge der längsten Palindrom-Teilzeichenfolge ermitteln müssen. Ein Palindrom-Teilstring kann als symmetrischer String verstanden werden. Aufgrund der Symmetrie ist die Grundidee die „Mittelerweiterungsmethode“, das heißt, die Zeichenfolge wird nacheinander durchlaufen und dann auf beide Seiten des Zeichens erweitert. Wenn die Zeichen auf beiden Seiten gleich sind, ist dies der Fall In der Retlen-Variablen aufgezeichnet, erhalten wir schließlich einfach die maximale Länge zurück. Zeichnen Sie zum besseren Verständnis ein Bild:
Darüber hinaus muss bei der Analyse des Beispiels auch auf den Unterschied zwischen ungeraden und geraden Zahlen geachtet werden, sodass der nächste Schritt die Programmimplementierung ist.
Zunächst wird gemäß der „Center-Expansion-Methode“ der Ideenanalyse die Zeichenfolge von der zentralen Station aus durchlaufen und erweitert. Die erhaltenen Retlen werden dann kontinuierlich mit Retlen verglichen und aktualisiert Zahlen bzw. gerade Zahlen Finden Sie den Maximalwert und vergleichen Sie ihn schließlich, um den endgültigen Maximalwert zu erhalten, und geben Sie ihn zurück.
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 ;
}
};
Nachdem Sie die Frage gelesen haben, wissen Sie, dass Sie für den Kauf- und Verkaufsmechanismus einer Aktiengruppe nur einmal kaufen und verkaufen können. Lassen Sie uns den maximalen Gewinn ermitteln, den Sie erzielen, egal wann Sie kaufen oder verkaufen, egal wie viel du verlierst, das heißt, es gibt keinen Gewinn, dann Ausgabe 0 Das ist es. Die Grundidee besteht dann darin, die Gewinndifferenz jeder Gruppe mithilfe der Aufzählungs-/Brute-Force-Methode zu ermitteln und den Maximalwert zurückzugeben. Nach dem Ausprobieren wird festgestellt, dass die zweischichtige For-Methode eine Zeitüberschreitung aufweist und dieses Problem begrenzt ist 1 ms zum Lösen. Daher ist eine Optimierung basierend auf der Brute-Force-Methode erforderlich, daher wird auch die Brute-Force-Methode geschrieben. Dann wurde das Backtracking zu oft wiederholt, Optimierung, Denken und Entdecken, wenn wir darüber nachdenken Umgekehrt, denken Sie zuerst über den Verkauf nach. Dann müssen Sie nur den Mindestwert vor dem Verkaufsargument ermitteln, und die erhaltene Differenz ist die maximale Differenz, was bedeutet, dass Sie sie nur einmal durchlaufen müssen. Der nächste Schritt ist die Programmumsetzung.
Zunächst werden gemäß der Brute-Force-Methode alle Situationen aufgezählt, um die maximale Differenzausgabe zu ermitteln. Bei dieser Frage tritt eine Zeitüberschreitung auf. Es muss also optimiert werden.
#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;
}
Basierend auf der oben genannten Brute-Force-Methode wird eine Optimierung durchgeführt, um sie vollständig zu verstehen. Basierend auf der Ideenanalyse wird ein Demonstrationsdiagramm erstellt:
Um das Programm zu implementieren, schreiben Sie dann die Eingabe nach Bedarf, definieren Sie dann minval, um arr[0] als angenommenen Mindestwert für den Durchlaufvergleich und die Aktualisierung zu initialisieren, und definieren Sie dann einen maxSub, um die maximale Differenz von minval beim Durchlauf zur i-Position darzustellen , was es wert ist Beachten Sie beim Durchlaufen die Reihenfolge von minval und maxSub. Suchen Sie zuerst den Mindestwert minval und dann 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;
}
Nachdem Sie die Frage gelesen haben, wissen Sie, wie viele Wege es nach bestimmten Regeln maximal gibt, um von Punkt A nach Punkt B zu gelangen. Bei der Analyse der Frage müssen Sie wissen, dass Sie nach bestimmten Regeln nach rechts oder nach unten gehen können, was die Idee der dynamischen Programmierung von dp hervorruft. Bei der Frage müssen Sie auch auf den Kontrollpunkt achten des Pferdes kann nicht bewegt (besucht) werden, d. h. der Ritter im Schach. Die durch die diagonale „Sonne“ auf den Koordinaten entworfenen Punkte, einschließlich des Startpunkts des Pferdes, werden Kontrollpunkte genannt. Unter diesen ist das Pferd ein zu Beginn angegebener fester Punkt (x, y), und die Frage gibt auch die Beziehung zwischen dem Sprungpunkt des Pferdes und dem Startpunkt des Pferdes an. Darüber hinaus ist zu beachten, dass gemäß dem Beispiel und dem Schachbrett die Größe des Schachbretts (n+1) beträgt.(m+1)。
Basierend auf der obigen Analyse können wir daher Folgendes schlussfolgern:
(1) Sie können DP-Ideen für die dynamische Programmierung verwenden, um Probleme zu lösen.
(2) Der Kontrollpunkt des Pferdes umfasst neben der diagonalen „Sonne“ auch seine eigene Startposition;
(3) Die Größe des Schachbretts beträgt (n+1).(m+1).
Daher kehren wir nach der Analyse der Aufmerksamkeitspunkte zur dp-Zustandsdarstellung und Zustandsübergangsgleichung der dynamischen Programmierung zurück;
Basierend auf den Laufregeln des Themas wird der Zustand dp[i][j] so definiert, dass er Folgendes darstellt: Es gibt höchstens mehrere Pfade zu dieser Position;
Leiten Sie die Zustandsübergangsgleichung her: dp[i][j] = d[i][j-1] + d[i-1][j];
Beachten Sie außerdem, dass, wenn die Startposition von Punkt B mit der Startposition des Pferdes oder dem Kontrollpunkt übereinstimmt und die Oberseite und die linke Seite von Punkt B, also dem Kontrollpunkt, alle blockiert sind, dies im obigen Extremfall der Fall ist , zu diesem Zeitpunkt dp[i] [j] = 0; Dann ist der nächste Schritt die Programmimplementierung.
Schreiben Sie zunächst die Eingabe gemäß der Analyse der Idee, definieren und öffnen Sie das dp-Array (zwei Fallstricke werden später besprochen) und entsprechend der Größe des Schachbretts, um die Koordinaten einheitlich beschreiben zu können, ein Extra Hier werden Zeile und Spalte geöffnet, dann müssen x und y zugeordnet werden. Legen Sie einfach die Koordinaten +=1 fest, untersuchen Sie dann das Initialisierungsproblem von dp und zeichnen Sie ein Bild, um es klarer zu machen:
Anschließend wird das eigentliche zweidimensionale Array von [1, n+1] und [1, m+1] durchlaufen, wobei die Verarbeitung extremer Situationen ständig beurteilt und schließlich dp[n+1][m+1] ausgegeben wird. Zu diesem Zeitpunkt gibt es kein Problem mit der Idee. Die zusammenfassenden Schritte sind wie folgt:
(1), Zuordnung der Koordinaten von x und y;
(2) Initialisieren Sie dp[0][1] = 1 oder dp[1][0] = 1 gemäß der Array-Definition (öffnen Sie eine weitere Ebene);
(3) Durchlaufen Sie das zweistellige Array und achten Sie dabei auf die Grenzkontrolldurchquerung von [1, n+1] und [1, m+1];
a. Ermitteln Sie Extremsituationen: 1. Der Kontrollpunkt des Pferdes blockiert den Weg. 2. Zufallsproblem.
b. Normale Ausführungszustandsübergangsgleichung: dp[i][j] = d[i][j-1] + d[i-1][j];
(4) Geben Sie schließlich dp[n+1][m+1] aus.
Darüber hinaus bestehen die beiden oben genannten Fallstricke darin, dass die Übermittlung fehlschlägt und ich feststelle, dass die Daten außerhalb des zulässigen Bereichs liegen. Daher ist es am besten, Long Long zum Öffnen des Arrays zu verwenden. Ein weiterer Fallstrick ist der Größenbereich von Die Öffnung ist zu groß. Die erste Etage wird genutzt, daher muss sie mindestens größer oder gleich 22 sein. Bisher konnten mit dp[21][21] nicht alle Anwendungsfälle abgedeckt werden.
#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;
}
längster Palindrom-Teilstring
Der beste Zeitpunkt zum Kauf und Verkauf von Aktien (1)
[NOIP2002 Popularization Group] Crossing the River Pawn
Er widmet sich seit mehr als 30 Jahren der Technologieforschung und beherrscht verschiedene Sprachen wie Java, Linux, Javascript, PHP, CSS usw. Er hat viele Beiträge im Open-Source-Bereich geleistet Entwicklerdokumentationsstation, um einige Themen in der Technologieentwicklung als zukünftige Referenz zu teilen
