- 题目描述:
-
给定一个大小为n的数组,数组的元素a[i]代表第i天的股票价格。
设计一个算法,计算在最多允许买卖k次(一买一卖记为一次)的条件下的最大收益。
需要注意的是,你不能同时拥有两份股票。也就是说在下次买入前,你必须把手头上原有的股票先卖掉。
- 输入:
-
输入可能包含多个测试案例。
对于每个测试案例,输入的第一行为两个整数n和k(1<=n,k<=1000)。
输入的第二行包括n个整数,范围在[0,10000),代表数组中的元素。
- 输出:
-
对应每个测试案例,输出最大获益。
- 样例输入:
-
5 1 3 4 5 1 4 7 2 1 2 3 5 6 1 7
- 样例输出:
-
3 11
一个简单的DP, 转移方程是:
f (i ,k ) = max{ f (i-1,k) , max { f( j,k-1) + prices[i]-prices[ j] | 0<=j<i } } ,
即,第i天不做生意,那么是f(i-1,k),或者第i天要卖,那么这次买应该来自第j 天,所以是 f(j,k-1) +prices[i] - prices[j] ,然后取最大值。
这个复杂度是 O ( N2 *K )的,很明显看到递归式中 后面枚举 j 的过程可以用单调队列优化的,这样最后复杂度是 O ( N * K ) 的。
先来个最直观的没有优化的好了嘛:
#include<iostream> #include<cstdio> #include<vector> #include<string> #include<cstring> #include<climits> #include<queue> #include<map> #include<algorithm> using namespace std; int main() { int n,k; while(scanf("%d%d",&n,&k)!=EOF) { vector<vector<int> > dp(n,vector<int>(k+1,0)); vector<int> prices(n,0); for(int i=0;i<n;i++) scanf("%d",&prices[i]); for(int i=1;i<n;i++) { for(int t=1;t<=k;t++) { int mx=dp[i-1][t]; for(int j=i-1;j>=0;j--) mx=max(mx,dp[j][t-1]+prices[i]-prices[j]); dp[i][t]=mx; } } printf("%d\n",dp[n-1][k]); } }
然后发现居然一个用例都过不了,全超时,真是。。。不好说什么了,一个月赛几道题的其中一道,不至于这么卡数据吧。。。这月赛难度太大了吧。。。
然后就老老实实写个优化的呗,还是比较直观,用 preMax[k] 表示这个最小值。
关于单调队列的优化,同学们可以去找找资料来看,超级有用,一般都能把复杂度降低一个 N.
#include<iostream> #include<cstdio> #include<vector> #include<string> #include<cstring> #include<climits> #include<queue> #include<map> #include<algorithm> using namespace std; int main() { int n,k; while(scanf("%d%d",&n,&k)!=EOF) { vector<vector<int> > dp(n,vector<int>(k+1,0)); vector<int> prices(n,0); vector<int> preMax(k+1,0); for(int i=0;i<n;i++) scanf("%d",&prices[i]); for(int i=0;i<=k;i++) preMax[i]=-prices[0]; for(int i=1;i<n;i++) { preMax[0]=max(preMax[0],dp[i][0]-prices[i]); for(int t=1;t<=k;t++) { int mx=dp[i-1][t]; mx=max(mx,preMax[t-1]+prices[i]); preMax[t-1]=max(preMax[t-1],dp[i][t-1]-prices[i]); dp[i][t]=mx; } } printf("%d\n",dp[n-1][k]); } }