CF724E Goods transportation 最小割 DP
照惯例CF的题不放原题链接。。。
题意:一个序列上有n个点,每个点有权值pi和si。表示这个点一开始有pi个物品,最多可以卖出si个物品,每个点都可以把物品向编号更大的点运输,但是对于i < j的任意点对(i, j)最多从i到j运c个物品。求最多能卖出多少个物品。
题解:
如果不考虑数据范围的话,可以直接用网络流建图。s向每个点连流量为pi的边,表示一开始有pi的流量,每个点i向满足i < j的点j连流量为c的边,表示最多运送c个物品,每个点向t连流量为si的边,表示最多可以卖si个物品。
最大流即为答案。
但是这题数据范围过大,无法用网络流跑过,观察到这个图比较特殊,即如果我们知道了哪些点属于S集合(S在残余网络中可以到达的点),哪些点属于T集合,就可以直接算出最小割。
即$ans = \sum_{i \in S}{s_{i}} + \sum_{i \in T}{p_{i}} + \sum_{i \in S}\sum_{j \in T}{c}$
解释一下为什么是这样,应该是比较好理解的,从最小割这个角度来理解。
如果一个点属于S,那么它肯定要断开与t的边,所以加上$s_{i}$,
如果一个点属于T,那么它肯定要断开与s的边,所以加上$p_{i}$,
如果一个点属于S,另一个点属于T,那么这两个点之间的边肯定要断开。
因此我们设f[i][j]表示前i个点有j个属于S集的最小代价。
那么如果这个点i我们划分到S集合里面,我们就加上$s_{i}$的代价。
否则加上$p[i] + j \cdot c$的代价,$j \cdot c$表示这个点要与之前被划分到S集合里面的j个点都断开联系,因为边权都是c,所以代价就是$j \cdot c$.
转移的时候注意一下j从0开始枚举。
#include<bits/stdc++.h>
using namespace std;
#define R register int
#define AC 10010
#define LL long long int n;
LL c, ans = 1e18;
LL f[][AC], s[AC], p[AC]; inline int read()
{
int x = ;char c = getchar();
while(c > '' || c < '') c = getchar();
while(c >= '' && c <= '') x = x * + c - '', c = getchar();
return x;
} inline void upmin(LL &a, LL b){
if(b < a) a = b;
} void pre()
{
n = read(), c = read();
for(R i = ; i <= n; i ++) p[i] = read();
for(R i = ; i <= n; i ++) s[i] = read();
} void work()
{
int now = ;
for(R i = ; i <= n; i ++)
{
now ^= ;
memset(f[now], , sizeof(f[now]));
for(R j = ; j <= i; j ++)
if(!j) f[now][j] = f[now ^ ][j] + p[i];
else f[now][j] = min(f[now ^ ][j] + p[i] + j * c, f[now ^ ][j - ] + s[i]);
}
for(R i = ; i <= n; i ++) upmin(ans, f[now][i]);
printf("%lld\n", ans);
} int main()
{
freopen("in.in", "r", stdin);
pre();
work();
fclose(stdin);
return ;
}
最新文章
- 求解第N个素数
- 关于一个sql的优化分析
- R语言-Kindle特价书爬榜示例 &; 输出HTML小技巧
- Oracle分页查询=======之伪列的使用
- 学习mongo系列(二) 新建数据库,collection ,insert(),save()
- k.NIO方式SSL通道流程
- Leetcode#76	Minimum Window Substring
- Oracle全表扫描
- [置顶] 蓝牙基础知识进阶——Physical channel
- 【STL__set_的应用】
- MUI跳转页面传值
- Aerospike | Aerospike Chinese
- hdoj 2183 奇数阶魔方(II) 【模拟】+【法】
- vue实现标签云效果
- 文本分类学习 (七)支持向量机SVM 的前奏 结构风险最小化和VC维度理论
- Python内置函数(52)——range
- null引用,有时候是实现了父类的方法,方法体没写任何实现
- 链路聚合trunk实现
- vue单页应用添加百度统计
- php中Redis的扩展