79、电影放映计划.docx

解题思路

题目给定时间周期和所有电影的时间长度以及利润，是一个给定空间的最大价值问题，简直就是标准的背包问题！只是换了换名词和描述而已。既然是背包问题，我们自然可以使用动态规划进行求解。

对于标准的背包问题，我们可以定义一个状态数组?dp，其中dp[i]?表示在第?i?分钟时获得的最大利润。但是考虑到两个电影之间是有时间间隔的，并且第一个电影之前和最后一个电影之后是不需要等待时间的，所以我们不妨将间隔时间也算入电影时长，并且考虑到最后一个电影之后不需要考虑延时，所以我们将可支配的时间也延长一个间隔时间来兼容最后一个电影的最后的多余的间隔时间即可。完成上述处理后即可简化为标准的背包问题。

对于每一部电影，我们需要决定是否放映它。如果我们放映第?ii?部电影，那么在第?ii?分钟时，我们可以选择放映它之前的一部电影，或者不放映任何电影。因此，我们可以得到状态转移方程：

dp[i]=max(dp[i?Tj]+Pj,dp[i])

其中?T_jTj?和?P_jPj?分别表示第?j?部电影的持续时长和利润。

我们从左到右遍历每一分钟，计算当前分钟时获得的最大利润。最终，dp[M]?即为所求的最大利润。

时间复杂度为?O(MN)，其中?M?为电影的总时长，N?为电影的数量。

AC_Code

C++

#includebits/stdc++.h

usingnamespacestd;

intmain(){

intM,N;

cinMN;

vectorintT(N),P(N);

for(inti=0;iN;i++){

cinT[i]P[i];

}

intK;

cinK;

M+=K;

for(inti=0;iN;i++)

T[i]+=K;

vectorintdp(M+1,0);

for(inti=1;i=M;i++){

dp[i]=dp[i-1];

for(intj=0;jN;j++){

if(i=T[j])

dp[i]=max(dp[i],dp[i-T[j]]+P[j]);

}

}

coutdp[M]endl;

return0;

}