题解 P2517 【[HAOI2010]订货】

这道题应该有以下几种做法： - 贪心 - 费用流 - 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} }}$ 怎样，妙不妙！ --- ## 好了上代码！ ```cpp #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~~ ### 顺便问一句dalao们觉得Latex用哪种配色最好看？我感觉红蓝比较好