题目

??点这里看题目。

分析

??首先不难想到一个网络流的做法。
??新建源点\(S\)和汇点\(T\)。对于每个点\(i\)，连接\((S,i)\)，流量为\(p_i\)；连接\((i,T)\)，流量为\(s_i\)。对于\(i<j\)，连接\((i,j)\)，流量为\(c\)。答案即为这个图的最大流。
??这样做是\(O(n^4)\)的。当然会\(T\)。
??考虑优化。根据最大流最小割定理，我们考虑哪些边会满流被割掉。发现对于\(i\)而言，这与之前的点的所属集合的情况相关。因此可以得到状态：
??\(f(i,j)\)：前\(i\)个点，有\(j\)个点在\(S\)集合的最小割。
??转移就是考虑当前的点所属的集合的情况：

??时间\(O(n^2)\)，空间可以滚动数组优化到\(O(n)\)。

代码

#include <cstdio>

typedef long long LL;

const LL INF = 0x3f3f3f3f3f3f3f3f;
const int MAXN = 1e4 + 5;

template<typename _T>
void read( _T &x )
{
	x = 0;char s = getchar();int f = 1;
	while( s > ‘9‘ || s < ‘0‘ ){if( s == ‘-‘ ) f = -1; s = getchar();}
	while( s >= ‘0‘ && s <= ‘9‘ ){x = ( x << 3 ) + ( x << 1 ) + ( s - ‘0‘ ), s = getchar();}
	x *= f;
}

template<typename _T>
void write( _T x )
{
	if( x < 0 ){ putchar( ‘-‘ ); x = ( ~ x ) + 1; }
	if( 9 < x ){ write( x / 10 ); }
	putchar( x % 10 + ‘0‘ );
}

template<typename _T>
_T MIN( const _T a, const _T b )
{
	return a < b ? a : b;
}

LL f[MAXN];
int p[MAXN], s[MAXN];
int N, c;

int main()
{
	read( N ), read( c );
	for( int i = 1 ; i <= N ; i ++ ) read( p[i] );
	for( int i = 1 ; i <= N ; i ++ ) read( s[i] );
	for( int i = 1 ; i <= N ; i ++ ) f[i] = INF;
	for( int i = 1 ; i <= N ; i ++ )
		for( int j = i ; ~ j ; j -- )
			f[j] = MIN( f[j] + 1ll * j * c + p[i], j ? ( f[j - 1] + s[i] ) : INF );
	LL ans = INF;
	for( int i = 0 ; i <= N ; i ++ ) ans = MIN( ans, f[i] );
	write( ans ), putchar( ‘\n‘ );
	return 0;
}

[CF724E]Goods Transportation

原文：https://www.cnblogs.com/crashed/p/12686312.html