题解 P2517 【[HAOI2010]订货】

interestingLSY · 2018-02-10 21:11:42 · 题解

这道题应该有以下几种做法：

贪心
费用流
dp

现在我要讲讲dp做法！

状态？

令 {\color{blue} { dp_{i,j} }} 表示第 i 个月,卖之后库中还有 j 包辣条 ( 辣条什么鬼0v0 ) 的最小花费

注意一定是卖之后

状态转移？

假设我们现在要处理的状态为 {\color{blue} { dp_{i,j} }}

假设第 i-1 个月卖完后还有 k 包辣条，那么我们可以知道第 i 个月买了 {\color{blue}{j+U_i-k}} 包辣条（想想为啥？）

也就是说我们需要多花 {\color{blue}{(j+U_i-k)\cdot D_i\ +\ k \cdot m}} 元。

很自然，方程出来了：

{\color{red}{ dp_{i,j} \ = \ min \left\{\ dp_{i-1,k}+(j+U_i-k)\cdot D_i\ +\ k \cdot m \right\} }}

(\ 0 \leq k \leq min(j+U_i,S)\ )

然而。。。

黑恶势力登场.jpg

这样dp的话，状态数为 O(nS) 转移复杂度为 O(S) 总体复杂度为 O(nS^2) 最坏情况下为 5 \times 10^9。。。

别放弃啊咱们一起优化

提出常数项后方程式变为:

\color{red} dp_{i,j} \ = \ \color{green}min \left\{\ dp_{i-1,k}-k\cdot D_i\ +\ k \cdot m \right\}\color{red}\ +\ (j+U_i)\cdot D_i

(\ 0 \leq k \leq min(j+U_i,S)\ )

注意到原谅色的那部分了吗？没错，你会发现那个式子与 j 无关！而正是那个式子占用了 O(S) 的复杂度！

下面为了表述方便，我们设

\color{blue}F_{i,k}\ = \ dp_{i-1,k}-k\cdot D_i\ +\ k \cdot m

\color{red}M_{i,j}\ = \ min\left\{ F_{i,z}\right\}\ (0 \leq z \leq j)

这样方程式就等价于

dp_{i,j}\ =\ \color{red}M_{i,j} \color{black}+(j+U_i)\cdot D_i

再观察 \color{red}M_{i,j} ,可以发现它的另一种表示方法：

\color{red}M_{i,j}\ =\ min(M_{i,j-1},F_{i,j})$ $(j \neq 0)

\color{red}M_{i,j}\ =\ F_{i,j}$ $(j = 0)

所以你发现了什么？若把 \color{red}M_{i,j} 的值存起来，我们可以在 O(1) 的时间内求出 \color{red}M_{i,j}

总复杂度就变成了 O(nS)

再多说两句：

你发没发现，我这种做法其实是两个dp!!

其中一个用于计算 \color{red}M_{i,j}

另一个用于计算 {\color{blue} { dp_{i,j} }}

怎样，妙不妙！

好了上代码！

#include <bits/stdc++.h>
#define INF (0x3f3f3f3f)
#define ll long long
#define Ms(_data) memset(_data,0,sizeof(_data))
#define Msn(_data,_num) memset(_data,_num,sizeof(_data))
using namespace std;
#define Mymax(a,b) if(a<b) a = b;
#define Mymin(a,b) if(a>b) a = b;
#define il inline
#define rg register
#define For(i,j) for( rg int (i) = 1 ; (i) <= (j) ; (i)++ )
#define For0(i,j) for( rg int (i) = 0 ; (i) < (j) ; (i)++ )
#define Forx(i,j,k) for( rg int (i) = (j) ; (i) <= (k) ; (i)++ )
#define Forstep(i,j,k,st) for( rg int (i) = (j) ; (i) <= (k) ; (i) += (st) )
/////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////
#define MAXN 60
#define MAXS 10010
int n,m,s;
int u[MAXN], d[MAXN];

int dp[MAXN][MAXS];
int mintmp[MAXN][MAXS];
// dp[i][j] 表示第i个月,卖之后库存为j的最小花费

il int F( int i , int k ){
    return dp[i-1][k] + k*m - k*d[i];
}
il void M( int i , int k ){
    if( k == 0 ) mintmp[i][k] = F(i,k);
    else mintmp[i][k] = min(mintmp[i][k-1],F(i,k));
}
il void Pre( int i ){
    Forx(j,0,s)
        M(i,j);
}

int main(){
    Msn(dp,INF);
    Msn(mintmp,INF);

    scanf("%d%d%d",&n,&m,&s);
    For(i,n) scanf("%d",&u[i]);
    For(i,n) scanf("%d",&d[i]);

    dp[0][0] = 0;
    For(i,n){
        Pre(i);
        For0(j,s+1){
            int klimit = min(j+u[i],s);
            dp[i][j] = mintmp[i][klimit] + (j+u[i])*d[i];
        }
    }

    int ans = dp[n][0];
    printf("%d\n",ans);

    return 0;
}

如果感觉题解有问题(包括但不限于错别字、程序有bug、式子打错了、我长得丑)，一定要在评论区提出！

~~没有问题就给个赞awa~~