給定一組函數f1 ... fn(離散時間)和時間限制(int)，應找到最大輸出，即在不同函數之間分配時間以最大化所用函數輸出的總和。

對于任何函數，任何時候的值表示如果用于所述時間的函數的總輸出。 即F(2)=函數的總輸出，如果使用2秒。 不是F(1)+ F(2)。

所有值(時間，函數輸出)都是整數。

我的當前算法通過檢查F(t)找到所有時間被放入一個函數的情況，將最大值與前一個最大M(t-1)+的所有可能輸出的最大值進行比較，找出可能損壞的最大值為每個可能的功能添加1秒(帶有已使用功能和時間的記錄)。

public int computeDamage(){

int totalTime = calculator.getTotalTime();

int numAttacks = calculator.getNumAttacks();

if(totalTime == 0) return 0;

int[] attackHist = new int[numAttacks];

return maxDamage(numAttacks, attackHist, 1, totalTime, 0);

}

public int maxDamage(int numAttacks, int[] attackHist, int start, int end, int max) {

//get the max of all the values at f(start), save the attack

int maxF = -1, attack = -1;

for(int i = 0; i < numAttacks; i++) {

int dam = calculator.calculateDamage(i, start);

if(dam > maxF) {

maxF = dam;

attack = i;

}

}

//if start isn't 1, get the max of all possible values added to the attackHist

int maxH = -1, attackH = -1;

if(start > 1) {

for(int j = 0; j < numAttacks; j++) {

int dChange = -1;

if(attackHist[j] > 0) dChange = calculator.calculateDamage(j, attackHist[j]+1) - calculator.calculateDamage(j, attackHist[j]);

else dChange = calculator.calculateDamage(j, attackHist[j]+1);

if((max + dChange) > maxH) {

maxH = max + dChange;

attackH = j;

}

}

//if max is greater, reset attackHist. Otherwise, add 1 to used attack

if(maxF > maxH) {

Arrays.fill(attackHist, 0);

attackHist[attack] = start;

max = maxF;

} else {

attackHist[attackH]++;

max = maxH;

}

} else {

//just set the max to maxF

max = maxF;

attackHist[attack] = 1;

}

if(end == start) return max;

else return maxDamage(numAttacks, attackHist, start+1, end, max);

}

輸入12.in

20 12

0 3 4 7 9 12 12 14 15 15 17 19

2 5 6 9 11 12 15 15 16 19 21 22

1 4 6 8 9 11 13 14 16 18 21 22

1 4 4 4 5 5 6 8 9 11 12 14

0 3 4 5 7 10 12 13 15 17 20 20

1 3 5 5 8 10 10 12 14 15 16 18

1 1 3 5 7 8 10 11 11 13 14 16

1 1 2 2 2 3 6 7 10 11 11 12

1 3 5 5 7 7 8 11 11 12 14 16

0 1 4 5 6 9 10 11 12 12 15 18

3 5 5 7 8 10 12 12 14 15 15 16

3 5 6 9 12 12 13 14 15 18 21 21

1 2 3 4 7 9 10 12 12 15 18 18

3 4 5 7 8 10 12 13 13 16 17 20

3 5 7 7 10 11 14 16 17 18 21 23

0 1 4 7 7 8 10 12 13 13 14 16

2 3 3 6 8 9 12 15 17 18 20 21

0 2 3 3 6 8 9 10 13 15 17 17

1 2 4 7 9 9 9 11 14 14 17 19

3 5 6 7 10 11 12 12 13 16 17 19

第一行告訴我們有多少函數(20)和多少時間(12秒)來最大化輸出。

每一行都是一個定義為1到12 F(t)的函數，詳細說明了該函數在該點之前完成了多少損壞。

輸出應為31，但我的代碼輸出為30。