JSOI2016病毒感染

2021-03-25 16:24

阅读：486

标签：name long sizeof 感染 std 因此 algo size ons

题目链接：https://www.luogu.com.cn/problem/P5774

1.题目大意：

　　有1-n的村庄，每个村庄在不治疗的情况下每天死 a[ i ] 人，到达一个村庄可以治疗或跳过，若跳过，再回头时只能一直走回这个村庄，然后才能重新往前走，求最少死亡人数。

2.题目分析

　　我们定义f[ i ]为前 i 个村庄全部治好的最小代价。令j

　　预处理一下前缀和 s[] 数组

3.动态转移方程推导

（1） g数组：

　　　　　我们枚举起点 i 和区间长度 j ，则终点为 i + j

　　　　　 若救 i

　　　　　　　w[i+1][i+j] + (s[i+j]-s[i])*2;

　　　　　　　救 i 花了一天，从 i 走到 i+1 花了一天，总共耽误两天，死亡人数为 i+1 到 j 的总人数乘以 2，即 (s[i+j]-s[i])*2

　　　　　若跳过 i

　　　　　　　w[i+1][i+j] + 3*j*a[i]+s[i+j]-s[i]

　　　　　　　从 i 走到 j 再走回 i 并治疗从 i+1 到 j 的所有村庄，耗时 3*j 天。 i 村庄死亡 3*j*a[ i ];

　　　　　　　从 i 到 i+1 花了一天，死亡 s[i+j]-s[i]

　　综上 w[i][i+j] = w[i+1][i+j]+min((s[i+j]-s[i])*2, 3*j*a[i]+s[i+j]-s[i]);

（2）f数组

　　　　枚举终点 i 和回头点 j

f[i] = min(f[i], f[j]+w[j+1][i]+(3*(i-j-1)+i-j+1)*(s[N]-s[i]));

从 j+1 走到 i 回到 j+1，我们还需再到 i ，耗时 3*（i-（j+1））

　　　　从·j 走到 j+1 并治疗 j+1 到 i 的所有村庄耗时 i-j+1（不理解可以自己画线段图看一下）

　　　　共死亡(3*(i-j-1)+i-j+1)*(s[N]-s[i]))

4.最后附上代码

 1 #include
 2 #include
 3 #include
 4 #include
 5 typedef long long ll;
 6 using namespace std;
 7 const int maxn = 3010;
 8 ll a[maxn], s[maxn], f[maxn], w[maxn][maxn];
 9 int main(){
10     ll N; scanf("%lld", &N);
11     for(int i=1; i

JSOI2016病毒感染

标签：name long sizeof 感染 std 因此 algo size ons

原文地址：https://www.cnblogs.com/hzoi-poozhai/p/12657646.html

上一篇：java 从零开始手写 redis（六）redis AOF 持久化原理详解及实现

下一篇：搭建php环境

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：JSOI2016病毒感染
文章链接：http://soscw.com/index.php/essay/67936.html

亲，登录后才可以留言！

JSOI2016病毒感染

评论

热门文章

推荐文章

最新文章

置顶文章