Intel Code Challenge Final Round (Div. 1 + Div. 2, Combined) E. Goods transportation (非官方贪心解法)

时间：2021-03-03 06:40:13

题目链接：http://codeforces.com/contest/724/problem/E

题目大意：

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

解法一(官方解法)：

构造网络流,因为边太多,不可能直接跑最大流。 根据图的特殊性,考虑用dp求解最小割。

状态：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])。

最后答案就是min(dp[n][0...n])  时间复杂度O(n2)

代码：

#include <iostream>

#include <cstdio>

#include <cmath>

#include <cstring>

#include <algorithm>

#include <vector>

#include <map>

#include <cstdlib>

#include <set>

using namespace std;

#define X first

#define Y second

#define Mod 1000000007

#define N 10010

#define M 400010

typedef long long ll;

typedef pair<int,int> pii;

int n,c;

int s[N],p[N];

ll dp[][N];

int main()

{

    //freopen("in.in","r",stdin);

    //freopen("out.out","w",stdout);

    scanf("%d%d",&n,&c);

    for (int i=;i<=n;i++) scanf("%d",&p[i]);

    for (int i=;i<=n;i++) scanf("%d",&s[i]);

    int op=;

    for (int j=;j<=n;j++) dp[op][j]=1e18;

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

    {

        op^=;

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

        {

            if (j) dp[op][j]=min(dp[op^][j-]+s[i],dp[op^][j]+1ll*j*c+p[i]);

            else dp[op][j]=dp[op^][j]+p[i];

            //cout<<i<<" "<<j<<" "<<dp[op][j]<<endl;

        }

    }

    ll ans=1e18;

    for (int j=;j<=n;j++) ans=min(ans,dp[op][j]);

    printf("%I64d\n",ans);

    return ;

}

解法二：

同样是求最小割。但是利用了贪心的策略。分别求出有i个点和源点相连的 最小割。

假设已经有k-1个点与源点相连,现在要增加第k个点p。

1.对于这k-1个点中编号比p小的,假设有s个,在加入p之前,它们连到p的边肯定已经被割掉了,否则p也与源点相连。 如果加入p,那么这些边就没必要割掉了,从当前代价里减去。

2.对于这k-1个点中编号比p大的,假设有t个,在加入p之后,p连到它们的边是没有必要去割的。

3.对于编号比p大而且不在这k-1个点中的, p连到它们的边必须割去,否则它们也会与源点相连。

根据2,3     需要新割掉n-p-t条边,代价增加(n-p-t)*c；   根据1  代价减少s*c；

总的割边数变化是(n-p-t-s) =  n-p-(s+t) =  n-p-(k-1)= (n-p+1)-k.

把这个代价分为2个部分,一部分是n-p+1, 只和加入的点的编号有关 。一部分是-k,只和目前加入了几个点有关。

因此就可以贪心,每次选择n-p+1最小的点加入。

用一个multiset或者heap来维护最小值,时间复杂度O(nlogn)

代码：

#include <iostream>

#include <cstdio>

#include <cmath>

#include <cstring>

#include <algorithm>

#include <vector>

#include <map>

#include <cstdlib>

#include <set>

using namespace std;

#define X first

#define Y second

#define Mod 1000000007

#define N 10010

#define M 400010

typedef long long ll;

typedef pair<int,int> pii;

int n,c;

int p[N],s[N];

multiset<ll> st;

int main()

{

    //freopen("in.in","r",stdin);

    //freopen("out.out","w",stdout);

    ll ans,sum=;

    scanf("%d%d",&n,&c);

    for (int i=;i<=n;i++) scanf("%d",&p[i]),sum+=p[i];

    for (int i=;i<=n;i++) scanf("%d",&s[i]),st.insert(s[i]-p[i]+1ll*(n+-i)*c);

    ans=sum;

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

    {

        sum+= *st.begin()-1ll*i*c;

        st.erase(st.begin());

        ans=min(ans,sum);

    }

    printf("%I64d\n",ans);

    return ;

}

相关文章