傳送門

原Word文檔

題意：太長不給

---

這種題目一看就是區間DP

設$f_i$表示治愈了前$i$個村子的時候最少死了多少村民，又設前綴和為$sum_i$，通過枚舉折返時最后經過的村子$j$，并且提前計算$i+1$到$N$中死的村民數量，可以得到這樣子的方程：$$f_i=\min\limits_{j=1}^i\{f_{j-1}+g_{j,i}+(sum_N-sum_i) \times ((i-j) \times 3 + (i-j+1) + 1)\}$$其中$g_{j,i}$表示從$j$到$i$到$j$再到$i$的過程中最少的死的村民數量，保證$j$號點一開始沒有被治愈。

所以我們現在的關鍵點是求出$g_{j,i}$。考慮到在$j$與$i$之間的村子不知道是在$j$到$i$的路上被治愈還是在$i$到$j$的路上被治愈，所以考慮預處理這一項。

考慮設$h_{i,j}$表示從到達$i$點開始計算死亡人數，完成治愈完$i$到$j$村莊的人的任務的前提下最少的死亡人數。考慮第$i$個村莊是否在一開始就治愈，可以得到轉移方程：$$h_{i,j}=h_{i+1,j}+\min\{sum_j-sum_i + a_i \times ((j - i) \times 3) , (sum_j - sum_i) \times 2\}$$

那么$g_{i,j}=h_{i+1,j} + sum_j - sum_i + num_i \times ((j - i) \times 3)$，然后這道題就做完了（撒花

1 #include<bits/stdc++.h> 2 using namespace std; 3 4 inline int read(){ 5 int a = 0; 6 char c = getchar(); 7 while(!isdigit(c)) 8 c = getchar(); 9 while(isdigit(c)){ 10 a = (a << 3) + (a << 1) + (c ^ '0'); 11 c = getchar(); 12 } 13 return a; 14 } 15 16 long long f[3010][3010] , g[3010] , num[3010] , sum[3010] , N; 17 18 int main(){ 19 memset(g , 0x3f , sizeof(g)); 20 g[0] = 0; 21 N = read(); 22 for(int i = 1 ; i <= N ; i++) 23 sum[i] = (num[i] = read()) + sum[i - 1]; 24 for(int i = N - 1 ; i ; i--) 25 for(int j = i + 1 ; j <= N ; j++) 26 f[i][j] = f[i + 1][j] + min(sum[j] - sum[i] << 1 , sum[j] - sum[i] + num[i] * 3 * (j - i)); 27 for(int i = 1 ; i < N ; i++) 28 for(int j = i + 1 ; j <= N ; j++) 29 f[i][j] = f[i + 1][j] + sum[j] - sum[i] + num[i] * 3 * (j - i); 30 for(int i = 1 ; i <= N ; i++) 31 for(int j = i ; j ; j--) 32 g[i] = min(g[i] , g[j - 1] + f[j][i] + (sum[N] - sum[i]) * ((i - j << 2) + 2)); 33 cout << g[N]; 34 return 0; 35 }

?

轉載于:https://www.cnblogs.com/Itst/p/9832213.html

總結

以上是生活随笔為你收集整理的BZOJ4856 JSOI2016 病毒感染 区间DP的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。