b300.
貓貓的共鳴
Content
在一個月黑風高的晚上，一群夜貓子在牠們的秘密花園正在準備進行神秘儀式。
傳說當這個儀式所產生的能量達到一個神秘數值，天空就會落下無數的罐罐！
經過無數次的嘗試，牠們現在掌握了一些規律和能量的計算方式：
- 有 n 隻貓貓，會排成一條直線，並且不可以再移動。
- 每隻貓貓都有毛色的屬性 c 用一個正整數代表。
- 每隻貓貓都有能量的屬性 p 用一個正整數代表。
- 能量的共鳴是鏈式的，從左至右不會改變方向，但可以跳過某些貓貓不共鳴。
- 共鳴的條件有兩個：直接連接的貓貓毛色要不一樣，而且直接連接的兩隻貓貓能量之和一定要質數。
- 總能量為共鳴鏈的所有貓貓能量總和。
你是貓群中的能量預測科學員，要幫忙計算能量數值，藉此驗証你們現在掌握的理論是否正確。
Input
第一行一個正整數 n 表示參與儀式的貓貓 ( 1 <= n <= 10000 )
接著有 n 行，每行兩個正整數 c 和 p，用一個空格分隔
整數 c 代表毛色 ( 1 <= c <= n )
整數 p 代表能量 ( 1 <= p <= 106 )
Output
一個整數，代表共鳴能夠產生的最大能量。
Sample Input
#1
8 7 4 3 10 4 7 7 6 2 4 3 9 4 3 3 2
Sample Output
#1
30
測資資訊：
記憶體限制：
64
MB
不公開 測資點#0 (10%): 1.0s , <1K
不公開 測資點#1 (10%): 1.0s , <1K
不公開 測資點#2 (10%): 1.0s , <1K
不公開 測資點#3 (10%): 1.0s , <1K
不公開 測資點#4 (10%): 1.0s , <1M
不公開 測資點#5 (10%): 1.0s , <1M
不公開 測資點#6 (10%): 1.0s , <1M
不公開 測資點#7 (10%): 1.0s , <1M
不公開 測資點#8 (10%): 1.0s , <1M
不公開 測資點#9 (10%): 1.0s , <1M
不公開 測資點#0 (10%): 1.0s , <1K
不公開 測資點#1 (10%): 1.0s , <1K
不公開 測資點#2 (10%): 1.0s , <1K
不公開 測資點#3 (10%): 1.0s , <1K
不公開 測資點#4 (10%): 1.0s , <1M
不公開 測資點#5 (10%): 1.0s , <1M
不公開 測資點#6 (10%): 1.0s , <1M
不公開 測資點#7 (10%): 1.0s , <1M
不公開 測資點#8 (10%): 1.0s , <1M
不公開 測資點#9 (10%): 1.0s , <1M
Hint ：
| 貓貓1號 | 貓貓2號 | 貓貓3號 | 貓貓4號 | 貓貓5號 | 貓貓6號 | 貓貓7號 | 貓貓8號 | |
| 毛色 | 7 | 3 | 4 | 7 | 2 | 3 | 4 | 3 |
| 能量 | 4 | 10 | 7 | 6 | 4 | 9 | 3 | 2 |
| 最優選擇 | 1 | 1 | 1 | 1 |
- 貓貓1號, 貓貓2號, 是不能共鳴，因為能量和為15，不是質數。
- 貓貓2號, 貓貓3號, 可以共鳴，因為毛色不同, 且能量和為17，是質數。
- 貓貓3號, 貓貓4號, 可以共鳴，因為毛色不同, 且能量和為13，是質數。
- 貓貓2號, 貓貓6號, 也不能共鳴，因為毛色不同。
- 貓貓1, 2, 3號不能同時共鳴，因為要由左至右，不能由 1號 -> 3號 -> 2號，是不允許的。
最後，2號, 3號, 5號, 6號 這4隻貓產生共鳴時，會有最大值30能量。
測試 1 ~ 8：( 1 <= n <= 1000 )
測試點 9, 10：( 1 <= n <= 10000 )
Tags:
出處:
[管理者：
kulam@g.puic...(林建源)
]
| ID | User | Problem | Subject | Hit | Post Date |
沒有發現任何「解題報告」 |
|||||