有一群工人在工作，而你要負責管理他們的伙食。由於市價的波動，每天的伙食費皆不同，而你要決定他們哪些天可以吃東西，哪些天不能吃東西。如果他們連續吃東西越多天，他們的工作效率就會越高(賺越多錢)。當然，你也不能讓他們連續3天不吃東西，否則他們會生氣然後罷工。
現在你要規劃未來$n$天的伙食，已知未來$n$天每天的伙食費分別為$c_i$元，以及告訴你他們若連續吃東西$k$天，則當天能賺$p_k$元(由於連續待遇好太多天他們會怠惰，因此此數列不一定為遞增)，在他們不會罷工的條件下，請分配他們的伙食狀況使得淨賺的錢盡量多(收入-支出)。
第一行有一個正整數$n$代表天數。
第二行有$n$個正整數$c_i$代表未來$n$天的伙食費。
第三行有$n+1$個正整數$p_i$，分別代表連續吃東西$0\sim n$天時當天能賺的錢。
20%測資符合$1\le n\le 20$
60%測資符合$1\le n\le 1000$
100%測資符合$1\le n\le 5000$
所有測資符合$1\le c_i,p_i\le 10^5$
輸出一個整數，代表在不讓他們罷工的前提下，$n$天後最多能賺多少錢?(若賠錢則為負數)
範例測資1: 6 5 4 2 7 10 2 2 5 11 8 8 6 10 範例測資2: 5 4 2 6 7 5 1 2 3 4 5 5 範例測資3: 7 8 9 7 8 20 18 7 2 3 3 3 3 3 3 3
範例測資1: 20 範例測資2: 0 範例測資3: -5
範例測資1的最佳規劃是在第1,2,3,6天吃東西，則每天賺的錢分別為5-5,11-4,8-2,2,2,5-2，因此總合為20。
範例測資2的最佳規劃是在第2,5天吃東西，或者只在第3天吃東西，總淨賺皆為0。
範例測資3的最佳規劃是在第3,4,7天吃東西，總淨賺為-5。
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||