最小割dp Intel Code Challenge Final Round (Div. 1 + Div. 2, Combined) E

时间：2024-05-23 23:04:32

http://codeforces.com/contest/724/problem/E

题目大意：有n个城市,每个城市有pi件商品,最多能出售si件商品,对于任意一队城市i,j,其中i<j,可以从城市i往j运输最多c件商品。 求最多一共能卖出多少件商品。  n<=10000

思路：

定义dp(i,j)目前在位置i，删除了j个s(换说法就是：dp[i,j]表示前i个中有j个和源点相通的最小割)
转移：如果第i个点不和源点相连,那么pi这条边一定要割掉,并且之前和源点相连的j个点,每个点会有一条边连向第i个点,这些边也要割掉。
花费是dp[i-1][j]+p[i]+j*c;
如果第i个点和源点相连,那么si这条边肯定要割掉。 花费是dp[i-1][j-1]+s[i];
故dp[i][j]=min(dp[i-1][j]+p[i]+j*c,dp[i-1][j-1]+s[i])。

刚开始智障的定义错了，估计网络流写多了习惯性的拆点了

//看看会不会爆int!数组会不会少了一维！

//取物问题一定要小心先手胜利的条件

#include <bits/stdc++.h>

using namespace std;

#pragma comment(linker,"/STACK:102400000,102400000")

#define LL long long

#define ALL(a) a.begin(), a.end()

#define pb push_back

#define mk make_pair

#define fi first

#define se second

#define haha printf("haha\n")

const int maxn =  + ;

const LL inf = 1e18;

LL dp[][maxn];

LL p[maxn], s[maxn];

int n, c;

/*

定义dp(i, j)表示目前是第i个position，我们要删除j个p

如果这次删除的是s

dp(i, j) = min(dp(i, j), dp(i-1, j) + (i-j) * c + s[i]);

如果是删除p

dp(i, j+1) = min(dp(i, j+1), dp(i-1, j) + p[i])

///抱歉。上面的方法是错误的TAT。网络流做多了都一直习惯的把节点分开了

定义dp(i,j)目前在位置i，删除了j个s(换说法就是：dp[i,j]表示前i个中有j个和源点相通的最小割)

转移：如果第i个点不和源点相连,那么pi这条边一定要割掉,并且之前和源点相连的j个点,每个点会有一条边连向第i个点,这些边也要割掉。

花费是dp[i-1][j]+p[i]+j*c;

如果第i个点和源点相连,那么si这条边肯定要割掉。 花费是dp[i-1][j-1]+s[i];

故dp[i][j]=min(dp[i-1][j]+p[i]+j*c,dp[i-1][j-1]+s[i])。

*/

int main(){

    cin >> n >> c;

    for (int i = ; i <= n; i++)

        scanf("%lld", p + i);

    for (int i = ; i <= n; i++)

        scanf("%lld", s + i);

    int pos = ;

    for (int i = ; i <= n; i++){

        pos = pos ^ ;

        for (int j = ; j <= i; j++) dp[pos][j] = inf;

        for (int j = ; j < i; j++){

            dp[pos][j + ] = min(dp[pos][j + ], dp[pos ^ ][j] + s[i]);

            dp[pos][j] = min(dp[pos][j], dp[pos ^ ][j] + 1LL * j * c + p[i]);

        }

    }

    LL ans = inf;

    for (int i = ; i <= n; i++) ans = min(dp[pos][i], ans);

    cout << ans << endl;

    return ;

}

相关文章