發表新討論
#24990: 這題沒有特殊 judge...


allllllan123456 (God of Computer Science)

學校 : 國立臺灣大學
編號 : 13732
來源 : [140.109.20.138]
最後登入時間 ：
2021-07-08 17:41:52
c112. 00348 - Optimal Array Multiplication Sequence -- UVa348 | From: [1.167.40.194] | 發表日期 : 2021-04-10 15:26

如題，題目說有多組解可以輸出任何一組根本是騙人的，遇到多組解的時候只能盡量把矩陣往左邊塞，

換句話說，分組的時候要嘛是

for (int j=i; j<i+d; j++) {
    int temp = cost[i][j] + cost[j+1][i+d] + size[i-1]*size[j]*size[i+d];
    if (temp <= cost[i][i+d]) { /* use <= instead of <, since the problem has no special judge... */
     cost[i][i+d] = temp;
        separator[i][i+d] = j;
    }

 

}

要嘛就是

for (int j=i+d-1; j>=i; j++) {
    int temp = cost[i][j] + cost[j+1][i+d] + size[i-1]*size[j]*size[i+d];
    if (temp < cost[i][i+d]) { /* use <= instead of <, since the problem has no special judge... */
     cost[i][i+d] = temp;
        separator[i][i+d] = j;
    }

 

}
 
但不可以是
 
for (int j=i; j<i+d; j++) {
    int temp = cost[i][j] + cost[j+1][i+d] + size[i-1]*size[j]*size[i+d];
    if (temp < cost[i][i+d]) {
     cost[i][i+d] = temp;
        separator[i][i+d] = j;
    }

 

}
 
 
#24991: Re:這題沒有特殊 judge...


allllllan123456 (God of Computer Science)

學校 : 國立臺灣大學
編號 : 13732
來源 : [140.109.20.138]
最後登入時間 ：
2021-07-08 17:41:52
c112. 00348 - Optimal Array Multiplication Sequence -- UVa348 | From: [1.167.40.194] | 發表日期 : 2021-04-10 15:27

我懷疑這題 AC 率低根本就是這個原因...

 
ZeroJudge Forum