怎样做网站排名,如何做网站开发,上海建站模板网站,顺德网站建设效果昨天晚上#xff0c;初见它时#xff0c;月黑风高#xff0c;一个电脑#xff0c;一支笔#xff0c;一个人 今天秋高气爽#xff0c;再一瞥#xff0c;回眸间 我又来了#xff0c;honey题目题解代码实现题目 题解
首先这种 iii 天与前面 jjj 天有关联#xff0c;而…昨天晚上初见它时月黑风高一个电脑一支笔一个人 今天秋高气爽再一瞥回眸间
我又来了honey题目题解代码实现题目 题解
首先这种 iii 天与前面 jjj 天有关联而且让你求最后一天的极值 我们一定会联想到 DPDPDP 先搞定 dpdpdp 定义?
第一维毋庸置疑就是表示 iii 天接着思考一下第二维 jjj 1如果表示 iii 天买了或者卖了 jjj 股票就遇到了一个问题i−W−1i-W-1i−W−1 天的时候股票数又是多少呢? 难道我要再去用一重循环枚举吗显然不现实。
2如果表示 iii 天手上还拥有着 jjj 股票 iii 天已经操作完成了 那么 ±k±k±k 就是 i−W−1i-W-1i−W−1 的股票数了
综上 dp[i][j]:idp[i][j]:idp[i][j]:i 天手上的股票数为 jjj 时的最大收益。
最后输出 dp[n][0]dp[n][0]dp[n][0] 就可以了nnn 天的时候手上没有股票数肯定是最优解了不然你手上捏着股票又买卖不了拿来擦屁股吗 找到转移方程式? 这一天闲得慌不买也不卖 dp[i][j]dp[i−1][j](0≤j≤MaxP)dp[i][j]dp[i-1][j] (0≤j≤MaxP)dp[i][j]dp[i−1][j](0≤j≤MaxP) 这一天才开始玩股票只能去购进股票 dp[i][j]−j∗api(j−asi≤kj)dp[i][j]-j*ap_i(j-as_i≤kj)dp[i][j]−j∗api(j−asi≤kj) 自由权比较大手上有点资本也要购进 dp[i][j]dp[i−W−1][k]−(j−k)∗api(j−asi≤kj)dp[i][j]dp[i-W-1][k]-(j-k)*ap_i(j-as_i≤kj)dp[i][j]dp[i−W−1][k]−(j−k)∗api(j−asi≤kj) 该开始赚钱钱了卖一点股票出去 dp[i][j]dp[i−W−1][k](k−j)∗bpi(jk≤jbsi)dp[i][j]dp[i-W-1][k](k-j)*bp_i(jk≤jbs_i)dp[i][j]dp[i−W−1][k](k−j)∗bpi(jk≤jbsi)
在这四种情况下取一个 maxmaxmax 即可。
那么为什么i-W-1就是当前最优解呢
因为我们是一天一天递推过去的当前最优解会被传递过去
这也是我们DP需要完成的 分析这个 DPDPDP 的时间复杂度O(n3)O(n^3)O(n3)。
所以必须对 kkk 优化
我们就去拆一拆 case3 case4 的 DPDPDP 式 dp[i][j]dp[i−W−1][k]−(j−k)∗api(j−asi≤kj)dp[i][j]dp[i-W-1][k]-(j-k)*ap_i(j-as_i≤kj)dp[i][j]dp[i−W−1][k]−(j−k)∗api(j−asi≤kj)⇓\Downarrow ⇓dp[i][j]dp[i−W−1][k]k∗api−j∗api(j−asi≤kj)dp[i][j]dp[i-W-1][k]k*ap_i-j*ap_i(j-as_i≤kj)dp[i][j]dp[i−W−1][k]k∗api−j∗api(j−asi≤kj) 我们会发现 j∗apij*ap_ij∗api 是固定不变的。
也就是说真正影响 dp[i][j]dp[i][j]dp[i][j] 的是 dp[i−W−1][k]k∗apidp[i-W-1][k]k*ap_idp[i−W−1][k]k∗api
而且 dp[i−W−1][k]k∗apidp[i-W-1][k]k*ap_idp[i−W−1][k]k∗api 越大越好。
发现这个方程的实质是 k∈[j−asi,j)k∈[j-as_i,j)k∈[j−asi,j) 这个范围内取得的且只和 kkk 有关。
dp[i][j]dp[i−W−1][k](k−j)∗bpi(jk≤jbsi)dp[i][j]dp[i-W-1][k](k-j)*bp_i(jk≤jbs_i)dp[i][j]dp[i−W−1][k](k−j)∗bpi(jk≤jbsi)⇓\Downarrow⇓dp[i][j]dp[i−W−1][k]k∗bpi−j∗bpi(jk≤jbsi)dp[i][j]dp[i-W-1][k]k*bp_i-j*bp_i(jk≤jbs_i)dp[i][j]dp[i−W−1][k]k∗bpi−j∗bpi(jk≤jbsi)
我们会发现 j∗bpij*bp_ij∗bpi 是固定不变的。
也就是说真正影响 dp[i][j]dp[i][j]dp[i][j] 的是 dp[i−W−1][k]k∗bpidp[i-W-1][k]k*bp_idp[i−W−1][k]k∗bpi
而且 dp[i−W−1][k]k∗bpidp[i-W-1][k]k*bp_idp[i−W−1][k]k∗bpi 越大越好。
发现这个方程的实质是 k∈(j,jbsi]k∈(j,jbs_i]k∈(j,jbsi] 这个范围内取得的且只和k有关
结合以上两种情况就会联想到我们的单调队列了。
维护 kkk 的范围而且从大到小每次取队头 headheadhead 进行更值
这样就转化成了O(n2)O(n^2)O(n2)。 最后注意一下循环顺序
买股票就从小到大 0∼MaxP0\sim MaxP0∼MaxP
卖股票就从大到小 MaxP∼0MaxP\sim 0MaxP∼0
代码实现
#include cstdio
#include iostream
using namespace std;
#define MAXN 2005
int T, MaxP, W;
int ap, bp, as, bs;
int head, tail;
int deq[MAXN];
int dp[MAXN][MAXN];
int main() {scanf ( %d %d %d, T, MaxP, W ); W;dp[0][0] -MAXN * MAXN;for ( int i 1;i MaxP;i )dp[0][i] dp[0][i - 1];for ( int i 1;i T;i ) {scanf ( %d %d %d %d, ap, bp, as, bs );for ( int j 0;j MaxP;j )dp[i][j] dp[i - 1][j];for ( int j 0;j as;j )dp[i][j] max ( dp[i][j], -j * ap );if ( i W ) {head 1, tail 0;for ( int j 0;j MaxP;j ) {while ( head tail deq[head] j - as )head ;while ( head tail deq[tail] * ap dp[i - W][deq[tail]] j * ap dp[i - W][j] )-- tail;deq[ tail] j;dp[i][j] max ( dp[i][j], dp[i - W][deq[head]] deq[head] * ap - j * ap );}head 1, tail 0;for ( int j MaxP;j 0;j -- ) {while ( head tail deq[head] j bs )head ;while ( head tail deq[tail] * bp dp[i - W][deq[tail]] j * bp dp[i - W][j] )tail --;deq[ tail] j;dp[i][j] max ( dp[i][j], dp[i - W][deq[head]] deq[head] * bp - j * bp );}}}printf ( %d, dp[T][0] );return 0;
}
