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 
      
       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 = 10000 + 5;const LL inf = 1e18;LL dp[2][maxn];LL p[maxn], s[maxn];int n, c;/*定义dp(i, j)表示目前是第i个position，我们要删除j个p如果这次删除的是sdp(i, j) = min(dp(i, j), dp(i-1, j) + (i-j) * c + s[i]);如果是删除pdp(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 = 1; i <= n; i++)        scanf("%lld", p + i);    for (int i = 1; i <= n; i++)        scanf("%lld", s + i);    int pos = 0;    for (int i = 1; i <= n; i++){        pos = pos ^ 1;        for (int j = 0; j <= i; j++) dp[pos][j] = inf;        for (int j = 0; j < i; j++){            dp[pos][j + 1] = min(dp[pos][j + 1], dp[pos ^ 1][j] + s[i]);            dp[pos][j] = min(dp[pos][j], dp[pos ^ 1][j] + 1LL * j * c + p[i]);        }    }    LL ans = inf;    for (int i = 0; i <= n; i++) ans = min(dp[pos][i], ans);    cout << ans << endl;    return 0;}