Intel Code Challenge Final Round (Div. 1 + Div. 2, Combined) E - Goods transportation 最大流转最小割转dp

时间：2024-06-12 16:34:50

E - Goods transportation

思路：这个最大流-> 最小割->dp好巧妙哦。

#include<bits/stdc++.h>

#define LL long long

#define fi first

#define se second

#define mk make_pair

#define PII pair<int, int>

#define PLI pair<LL, int>

#define ull unsigned long long

using namespace std;

const int N = 1e4 + ;

const int inf = 0x3f3f3f3f;

const LL INF = 0x3f3f3f3f3f3f3f3f;

const int mod = 1e9 + ;

int n, c, cur, p[N], s[N];

LL dp[][N];

int main() {

    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]);

    memset(dp[cur], INF, sizeof(dp[cur]));

    dp[cur][] = ;

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

        cur ^= ;

        memset(dp[cur], INF, sizeof(dp[cur]));

        dp[cur][] = dp[cur^][] + p[i];

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

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

        }

        dp[cur][i] = dp[cur^][i-] + s[i];

    }

    LL ans = INF;

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

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

    return ;

}

/*

*/

相关文章