題解：2018級演算法第二次上機 Zexal的競賽
- 2019 年 10 月 18 日
- 筆記
題目描述：
樣例：
實現解釋：
一道需要一點思考的動態規劃題目
知識點：動態規劃，數據記錄
首先將題目描述調整：分別輸入不同分數的題目總分（便於後續計算），當獲得了i分數的總分後無法獲得i-1和i+1的總分。
於是便可先利用score[i]儲存i分數的總分數，用dp[i]儲存以前i個分數為範圍進行題目選擇時的最大可獲得分數。dp便是動態規劃所用的數組。
於是可得狀態轉移方程如下：
dp[0] = score[0]; dp[1] = score[1];
dp[i] = max(dp[i-2]+score[i],dp[i-1]);
0和1分直接初始化，而選擇前i個分數時的最大分數有兩種選擇：1.選擇前i-1個分數時的最大分數，2.選擇前i-2個分數時的最大分數加上當前分數的總分。
完善為完整的程式碼即可。
坑點：
多組輸入時需要重置score數組為0
考慮到dp是從前向後進行，因此注意要重置dp數組的0和1處的值
完整程式碼：
//動態規劃 zexal的競賽 #include <iostream> #include <algorithm>//引用max函數 using namespace std; long long dp[100010]; long long score[100010]; //注意如果多次輸入需要對score進行清空處理 int main() { ios::sync_with_stdio(false); int n,s; cin >> n;//題目個數 int top = 0;//最大的題目分數，防止無用的遍歷 for (int i = 0;i<n;i++) { cin >> s; score[s]+=s;//出現x次，則做完為x*s分 if(s>top) top = s; } dp[0] = score[0]; dp[1] = max(score[0],score[1]); for(int i = 2;i<=top;i++) { //具體狀態轉換方程見實現解釋 dp[i] = max(dp[i-2]+score[i],dp[i-1]); } //以所有分數題目為範圍的最大分數 cout << dp[top] << 'n'; }
