网站建设 乐视,wordpress排行榜前面小图标,wap门户网站,最常用的网站推广方式传送门 原Word文档 题意#xff1a;太长不给 这种题目一看就是区间DP 设$f_i$表示治愈了前$i$个村子的时候最少死了多少村民#xff0c;又设前缀和为$sum_i$#xff0c;通过枚举折返时最后经过的村子$j$#xff0c;并且提前计算$i1$到$N$中死的村民数量#xff0c;可以得到…传送门 原Word文档 题意太长不给 这种题目一看就是区间DP 设$f_i$表示治愈了前$i$个村子的时候最少死了多少村民又设前缀和为$sum_i$通过枚举折返时最后经过的村子$j$并且提前计算$i1$到$N$中死的村民数量可以得到这样子的方程$$f_i\min\limits_{j1}^i\{f_{j-1}g_{j,i}(sum_N-sum_i) \times ((i-j) \times 3 (i-j1) 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_{i1,j}\min\{sum_j-sum_i a_i \times ((j - i) \times 3) , (sum_j - sum_i) \times 2\}$$ 那么$g_{i,j}h_{i1,j} sum_j - sum_i num_i \times ((j - i) \times 3)$然后这道题就做完了撒花 1 #includebits/stdc.h2 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
