AtCoder ABC 013 A&B&C AtCoder - 013
A - A
private void solveA() {
char x = next().charAt(0);
out.println(x - 'A' + 1);
}
private void solveB() {
int a = nextInt();
int b = nextInt();
int wkA = Integer.max(a, b);
int wkB = Integer.min(a, b);
out.println(Integer.min(wkA - wkB, (10 - wkA) + wkB));
}
――Ich konnte alleine keine perfekte Punktzahl erzielen. Als ich mir das Editorial ansah, ...
private void solveC3() {
long n = nextLong();
long h = nextLong();
long a = nextLong();
long b = nextLong();
long c = nextLong();
long d = nextLong();
long e = nextLong();
long cost = Long.MAX_VALUE;
for (long i = 0; i <= n; i++) {
// long j = ((n - i) * e - h - b * i) / (d + e);
// long j = ceil((n - i) * e - h - b * i , d + e);
/*
*Die Formel zur Bestimmung des Sättigungsgefühls lautet wie folgt
* long currentManpuku = (h + i * b + j * d) - ((n - (i + j)) * e)
*Der Tag, an dem j eine einfache Mahlzeit in der obigen Formel hat.
* -Es spielt keine Rolle, ob es sich um eine einfache oder eine große Mahlzeit handelt. Entscheiden Sie also den Tag.
*Und ich,Sie müssen keine der Doppelschleifen in j verwenden.
* ->Wenn Sie die Anzahl der Tage für eine Mahlzeit festlegen, sollte die Anzahl der Tage für die andere Mahlzeit automatisch festgelegt werden.
*
*Das Sättigungsgefühl sollte nicht kleiner als 0 sein.
* (h + i * b + j * d) - ((n - (i + j)) * e) > 0
* (h + i * b + j * d) - (n - i - j) * e > 0
*Verwandeln Sie sich in die Form, die i oder j findet
*Hier verwandelt es sich in die Formel zum Finden von j
* h + i * b + j * d - n * e + i * e + j * e > 0
* j * d + j * e > - h - i * b + n * e - i * e
* j * (d + e) > (n - i) * e - i * b - h
* j > ((n - i) * e - i * b - h) / (d + e)
*Die minimale Anzahl von Tagen, um eine einfache Mahlzeit zu essen, könnte aus der obigen Formel abgeleitet werden.
*Voraussetzung ist jedoch
* -j ist 0 oder mehr (Wenn es negativ ist, müssen Sie keine einfache Mahlzeit zu sich nehmen)
* -j ist((n - i) * e - i * b - h) / (d + e) "Größer"Muss sein
** Muss größer sein als das Ergebnis, das auf der Grundlage des vorläufig beschlossenen i berechnet wurde
** Daher im Berechnungsergebnis+1
* ※((n - i) * e - i * b - h) / (d + e)Wenn das Ergebnis von 3 ist, ist der gültige Wert für j 4 oder mehr.
*/
long j = 0;
/*
*Wenn die positive / negative Beurteilung basierend auf dem Ergebnis der folgenden Formel vorgenommen wurde, wurde der Bruch so verschoben
* ((n - i) * e - i * b - h) / (d + e)
*Einmal wird die positive / negative Beurteilung nur vom Molekül vorgenommen (da der Nenner positiv ist, sollte nur das positive / negative des Moleküls ausreichen).
* (n - i) * e - i * b - h
* (i - n) * e + i * b + h < 0
*/
if ((n - i) * e - i * b - h > 0) {
/*
* j > ((n - i) * e - i * b - h) / (d + e)
*Damit((n - i) * e - i * b - h) / (d + e)Zu+1することZuよって
* j >Es wird gesagt.
* +1 oder j((n - i) * e - i * b - h) / (d + e)Wird nicht größer
*/
j = ((n - i) * e - i * b - h) / (d + e) + 1;
}
cost = Long.min(i * a + j * c, cost);
}
out.println(cost);
}
»Ich habe den letzten nicht bekommen
private void solveC2() {
long n = nextLong();
long h = nextLong();
long a = nextLong();
long b = nextLong();
long c = nextLong();
long d = nextLong();
long e = nextLong();
long cost = Long.MAX_VALUE;
//Wunderschönes Essen
for (long i = 0; i <= n; i++) {
//Einfache Mahlzeit
for (long j = 0; j <= n; j++) {
//Überprüfen Sie Ihre Fülle, indem Sie die Mahlzeiten für die verbleibenden Tage auslassen
long currentManpuku = (h + i * b + j * d) - ((n - (i + j)) * e);
//Diese Anzahl von Mahlzeiten wird übernommen, weil der Grad der Fülle größer als 0 ist
if (currentManpuku > 0) {
cost = Long.min(i * a + j * c, cost);
}
}
}
out.println(cost);
}
――Ich kann es überhaupt nicht schaffen
private void solveC() {
int n = nextInt();
int h = nextInt();
a = nextInt();
b = nextInt();
c = nextInt();
d = nextInt();
e = nextInt();
Map<Long, Long> memo = new HashMap<Long, Long>();
long res = recursiveC(n, 0, 0, h, memo);
out.println(res);
}
int a;
int b;
int c;
int d;
int e;
private long recursiveC(int n, long currentDay, long cost, long manpuku, Map<Long, Long> memo) {
if (manpuku <= 0) {
return Long.MAX_VALUE;
}
if (memo.getOrDefault(currentDay, Long.MAX_VALUE) < cost) {
return memo.get(currentDay);
} else {
memo.put(currentDay, cost);
}
if (currentDay >= n) {
return cost;
}
long val1 = recursiveC(n, currentDay + 1, cost + a, manpuku + b, memo);
long val2 = recursiveC(n, currentDay + 1, cost + c, manpuku + d, memo);
long val3 = recursiveC(n, currentDay + 1, cost, manpuku - e, memo);
long wk = (val2 <= val3) ? val2 : val3;
long wk2 = (val1 <= wk) ? val1 : wk;
memo.put(currentDay, wk2);
return wk2;
}
private void solveC4() {
int n = nextInt();
int h = nextInt();
int a = nextInt();
int b = nextInt();
int c = nextInt();
int d = nextInt();
int e = nextInt();
/*
* dp[i][j]:=Mindestwert der Nahrungsmittelkosten bei Zufriedenheit j am Tag i
*/
// final int DAY_MAX = 500005;
final int DAY_MAX = n + 5;
final int SATISFY_MAX = 100005;
long[][] dp = new long[DAY_MAX][SATISFY_MAX];
for (int i = 0; i < DAY_MAX; i++) {
Arrays.fill(dp[i], Long.MAX_VALUE);
}
dp[0][h] = 0;
/*
*Denken Sie an das Essen am nächsten Tag (DP zu verteilen)
*
*Gewöhnliche Mahlzeit: dp[i+1][j+b]=min(dp[i+1][j+b],dp[i][j]+a)
* ->
*Nächster Tag(i+1)Sättigung(j+b)Kosten bei(dp[i+1[j+b])Ist
*Der Tag davor(i)Sättigung(j)Kosten(dp[i][j])Fügen Sie ein zu hinzu(dp[i][j]+a)
*Von denen mit geringen Kosten (Anfangswert wird mit INF gefüllt)&(Weil es billiger sein kann, eine andere Mahlzeit zu wählen)
* ※i+1. Tag j+b kann voll sein oder nicht
*
*Einfache Mahlzeit: dp[i+1][j+d]=min(dp[i+1][j+d],dp[i][j]+c)
*Ohne Mahlzeiten: dp[i+1][j−e]=min(dp[i+1][j−e],dp[i][j])
* ->
* j−e >Beachten Sie, dass es 0 ist
*/
for (int i = 0; i < n; i++) {
for (int j = 0; j < SATISFY_MAX; j++) {
/*
*Dieser Tag existiert nicht
*/
if (dp[i][j] == Long.MAX_VALUE) {
continue;
}
/*
*Normale Mahlzeit am nächsten Tag
*/
dp[i + 1][j + b] = Long.min(dp[i + 1][j + b], dp[i][j] + a);
/*
*Die einfache Mahlzeit am nächsten Tag
*/
dp[i + 1][j + d] = Long.min(dp[i + 1][j + d], dp[i][j] + c);
/*
*Ohne Mahlzeiten
*/
if (j - e > 0) {
dp[i + 1][j - e] = Long.min(dp[i + 1][j - e], dp[i][j]);
}
}
}
long res = Long.MAX_VALUE;
/*
*Untersuchen Sie die Sättigung mit den niedrigsten Kosten am Tag n
*/
for (int i = 0; i < SATISFY_MAX; i++) {
res = Long.min(res, dp[n][i]);
}
out.println(res);
}
Recommended Posts