У меня есть проблема, подобная этой:
- Учитывая массив
a[n]
(с размером n <= 6 и элементами a [i] <= 60), за один раз вы можете уменьшить три (разные, <code>i1 != i2 != i3 != i1) элемента массива: один элемент на 9 a[i1]-=9
, один на 3 a[i2]-=3
, а оставшийся на 1 a[i3]-=1
. - Рассчитайте наименьшее время для уменьшения всех элементов массива выше до
a[i] <= 0
.
Итак, с этой проблемой, я думаю, я буду подсчитывать все возможные способы вычитать рекурсией и вернуть минимальное значение времени, это моя идея (неверно)
package Test;
import java.util.ArrayList;
public class hard {
static int minCount = Integer.MAX_VALUE;
static int count = 0;
static int time = 1;
static ArrayList<Integer> a = new ArrayList<>();
static boolean allDie(int[] a) {
int n = a.length;
for (int i = 0; i < n; i++) {
if (a[i]>0)
return false;
}
return true;
}
static void res(int x, int y, int z, int[] a, boolean[] visited) {
int x1 = x; int x2 = y; int x3 = z;
for (int i = 0; i < a.length; i++) {
if (!visited[i]) {
x1=i;
visited[i]=true;
break;
}
}
for (int i = 0; i < a.length; i++) {
if (!visited[i]) {
x2=i;
visited[i]=true;
break;
}
}
for (int i = 0; i < a.length; i++) {
if (!visited[i]) {
x3=i;
visited[i]=true;
break;
}
}
System.out.println(x1+" "+x2+" "+x3);
if (allDie(a)) {
System.out.println("_"+count);
minCount=Math.min(minCount,count);
if (x1>=0) a[x1]+=9;
if (x2>=0) a[x2]+=3;
if (x3>=0) a[x3]+=1;
if (x1>=0) visited[x1]=false;
if (x2>=0) visited[x2]=false;
if (x3>=0) visited[x3]=false;
count--;
return;
}
if (x1>=0) a[x1]-=9;
if (x2>=0) a[x2]-=3;
if (x3>=0) a[x3]-=1;
count++;
if (x1>=0 && a[x1]>0)
visited[x1] = false;
if (x2>=0 && a[x2]>0)
visited[x2] = false;
if (x3>=0 && a[x3]>0)
visited[x3] = false;
res(x1,x2,x3,a,visited);
count--;
if (x1>=0) a[x1]+=9;
if (x2>=0) a[x2]+=3;
if (x3>=0) a[x3]+=1;
if (x1>=0) visited[x1]=false;
if (x2>=0) visited[x2]=false;
if (x3>=0) visited[x3]=false;
}
static int mutaliskAttack(int[] scvs){
int n=scvs.length;
for (int i=0; i<n; i++)
res(i, i, i, scvs, new boolean[n]);
return minCount;
}
public static void main(String[] args) {
int[] e= {55, 60, 53};
System.out.println(mutaliskAttack(e)); // = 13
}
}
Но, кажется, не рассчитывается полностью, он возвращает 14 вместо 13 (правильный ответ), есть ли потери Кстати, когда я рекурсия использую 3 вершины одновременно, как это?
Если у вас есть лучшая идея вместо использования рекурсии, как я, вы можете помочь мне решить этот вопрос?