a163:
Q-2-12. 最接近的子矩陣和 (108高中全國賽)
內容
輸入一個整數二維矩陣A[M][N]，另外給了一個整數K，請計算哪一個子矩陣的和，也就是對所有1≤i≤j≤M and 1≤p≤q≤N，
最接近K而不超過K。M ≤50且M * N ≤300,000，每一個整數的絕對值不超過3,000。
輸入說明
每筆測資的第一行有ㄧ個正整數K；第二行有兩個正整數M 與 N。
接下來，由上而下，從左至右，有M行輸入，每一行有N個整數，每一個整數的絕對值不超過3,000，代表A[s][t]，同行整數間以空格隔開。
輸出說明
在所有子矩陣和中，最接近K但不超過K的和
範例輸入
#1
6 2 3 -1 -1 1 2 2 2
範例輸出
#1
6
測資資訊：
記憶體限制：
64
MB
公開 測資點#0 (11%): 1.0s , <10M
公開 測資點#1 (11%): 1.0s , <10M
公開 測資點#2 (11%): 1.0s , <10M
公開 測資點#3 (11%): 1.0s , <1M
公開 測資點#4 (11%): 1.0s , <1M
公開 測資點#5 (11%): 1.0s , <10M
公開 測資點#6 (11%): 1.0s , <10M
公開 測資點#7 (11%): 1.0s , <10M
公開 測資點#8 (12%): 1.0s , <10M
公開 測資點#0 (11%): 1.0s , <10M
公開 測資點#1 (11%): 1.0s , <10M
公開 測資點#2 (11%): 1.0s , <10M
公開 測資點#3 (11%): 1.0s , <1M
公開 測資點#4 (11%): 1.0s , <1M
公開 測資點#5 (11%): 1.0s , <10M
公開 測資點#6 (11%): 1.0s , <10M
公開 測資點#7 (11%): 1.0s , <10M
公開 測資點#8 (12%): 1.0s , <10M
提示 ：
對所有列的範圍[i, j]，把第i列到第j列”黏”起來變成一個一維陣列
標籤:
出處:
AP325
[管理者：
]
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||