AtCoder ABC 013 A&B&C AtCoder - 013
A - A
--Si traité comme char, il devient 0 avec X-'A'. Lorsque ʻA`, il vaut 1, vous pouvez donc ajouter +1.
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));
}
`` Je n'ai pas pu obtenir un score parfait par moi-même, alors quand j'ai regardé l'éditorial, ...
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);
/*
*La formule pour déterminer la satiété est la suivante
* long currentManpuku = (h + i * b + j * d) - ((n - (i + j)) * e)
*Le jour où j prend un repas simple dans la formule ci-dessus.
* -Peu importe qu'il s'agisse d'un simple repas ou d'un gros repas, alors décidez du jour.
*Et moi,Vous n'avez pas besoin d'utiliser l'une des doubles boucles de j.
* ->Si vous décidez du nombre de jours pour un repas, le nombre de jours pour l'autre repas doit être décidé automatiquement.
*
*La satiété ne doit pas être inférieure à 0,
* (h + i * b + j * d) - ((n - (i + j)) * e) > 0
* (h + i * b + j * d) - (n - i - j) * e > 0
*Parmi ceux-ci, transformez-vous en la forme qui trouve i ou j
*Ici, il se transforme en formule pour trouver 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)
*Le nombre minimum de jours pour manger un repas simple pourrait être dérivé de la formule ci-dessus.
*Cependant, comme condition
* -j est égal ou supérieur à 0 (s'il est négatif, vous n'avez pas besoin de manger un repas simple)
* -j est((n - i) * e - i * b - h) / (d + e) "Plus grande"Doit être
** Doit être plus grand que le résultat calculé sur la base du i provisoirement décidé
** Par conséquent, dans le résultat du calcul+1
* ※((n - i) * e - i * b - h) / (d + e)Si le résultat de est 3, la valeur valide pour j est 4 ou plus.
*/
long j = 0;
/*
*Lorsque le jugement positif / négatif a été fait sur la base du résultat de la formule suivante, la fraction a été décalée, donc
* ((n - i) * e - i * b - h) / (d + e)
*Une fois, le jugement positif / négatif est porté uniquement par la molécule (puisque le dénominateur est positif, seul le positif / négatif de la molécule devrait être suffisant)
* (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)
*Alors((n - i) * e - i * b - h) / (d + e)À+1することÀよって
* j >C'est dit.
* +1 ou j((n - i) * e - i * b - h) / (d + e)Ne grandira pas
*/
j = ((n - i) * e - i * b - h) / (d + e) + 1;
}
cost = Long.min(i * a + j * c, cost);
}
out.println(cost);
}
――Je n'ai pas eu le dernier
--Tourner une boucle au lieu d'absurdement récursif ―― En premier lieu, vous devriez manger autant que vous pouvez manger un repas normal et un repas simple, puis sauter le repas. ―― Apportez le dernier repas ―― Le nombre de jours pour sauter un repas est calculé à partir du nombre de jours où vous avez mangé un repas normal et du nombre de jours où vous avez mangé un repas simple.
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;
//Magnifique repas
for (long i = 0; i <= n; i++) {
//Repas simple
for (long j = 0; j <= n; j++) {
//Vérifiez votre satiété en sautant des repas pour les jours restants
long currentManpuku = (h + i * b + j * d) - ((n - (i + j)) * e);
//Ce nombre de repas est adopté car le degré de satiété est supérieur à 0
if (currentManpuku > 0) {
cost = Long.min(i * a + j * c, cost);
}
}
}
out.println(cost);
}
――Je ne peux pas du tout y arriver
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]:=Valeur minimale des dépenses alimentaires lorsque satisfaction j le jour 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;
/*
*Pensez au repas du lendemain (DP à distribuer)
*
*Repas ordinaire: dp[i+1][j+b]=min(dp[i+1][j+b],dp[i][j]+a)
* ->
*Le prochain jour(i+1)Satiété(j+b)Coût à(dp[i+1[j+b])Est
*Le jour d'avant(i)Satiété(j)Coût(dp[i][j])Ajouter un à(dp[i][j]+a)
*Parmi ceux-ci, celui avec le coût le plus bas (la valeur initiale est remplie avec INF)&(Parce qu'il peut être moins cher de choisir un repas différent)
* ※i+1er jour j+b peut ou peut ne pas être plein
*
*Repas simple: dp[i+1][j+d]=min(dp[i+1][j+d],dp[i][j]+c)
*Sans repas: dp[i+1][j−e]=min(dp[i+1][j−e],dp[i][j])
* ->
* j−e >Notez que c'est 0
*/
for (int i = 0; i < n; i++) {
for (int j = 0; j < SATISFY_MAX; j++) {
/*
*Ce jour n'existe pas
*/
if (dp[i][j] == Long.MAX_VALUE) {
continue;
}
/*
*Repas normal le lendemain
*/
dp[i + 1][j + b] = Long.min(dp[i + 1][j + b], dp[i][j] + a);
/*
*Le repas simple du lendemain
*/
dp[i + 1][j + d] = Long.min(dp[i + 1][j + d], dp[i][j] + c);
/*
*Sans repas
*/
if (j - e > 0) {
dp[i + 1][j - e] = Long.min(dp[i + 1][j - e], dp[i][j]);
}
}
}
long res = Long.MAX_VALUE;
/*
*Recherchez la satiété la moins coûteuse le jour n
*/
for (int i = 0; i < SATISFY_MAX; i++) {
res = Long.min(res, dp[n][i]);
}
out.println(res);
}
Recommended Posts