算是一个总结吧!
先来一个模板;
TYVJ 1305 最大子序和
题目描述
输入一个长度为n的整数序列,从中找出一段不超过M的连续子序列,使得整个序列的和最大。 例如 1,-3,5,1,-2,3 当m=4时,S=5+1-2+3=7 当m=2或m=3时,S=5+1=6输入输出格式
输入格式:第一行两个数n,m
第二行有n个数,要求在n个数找到最大子序和 输出格式: 一个数,数出他们的最大子序和输入输出样例
6 4 1 -3 5 1 -2 3
7
数据范围:
100%满足n,m<=300000
这个可以算是单调队列优化dp的模板题了吧;
令f[i]表示以i为结尾的连续子序的最大值;
所以, f[i] = min (sum[i] - sum[j]) ( i - m <= j <= i); sum 为前缀和;
即 f[i] = sum[i] - min(sum[j])( i - m <= j <= i);
显然可以用单调队列维护前缀最小值;
代码:
#include#include #include #include #include using namespace std;int n, m;int a[300010];int sum[300010];deque q;int ans;int main(){ cin >> n >> m; for(register int i = 1 ; i <= n ; i ++) { scanf("%d", &a[i]); sum[i] = sum[i-1] + a[i]; } for(register int i = 1 ; i <= n ; i ++) { while(!q.empty() && sum[q.front()] > sum[i]) q.pop_front(); q.push_front(i); while(!q.empty() && i - m > q.back()) q.pop_back(); if(i != 1) { ans = max(ans, sum[i] - sum[q.back()]); } else ans = max(ans, sum[i]); } cout << ans << endl; return 0; }
再来一道水题;
POJ1821 Fence
Description
Input
Input
N K L1 P1 S1 L2 P2 S2 ... LK PK SKSemnification
N -the number of the planks; K ? the number of the workers Li -the maximal number of planks that can be painted by worker i Pi -the sum received by worker i for a painted plank Si -the plank in front of which sits the worker iOutput
Sample Input
8 43 2 23 2 33 3 51 1 7
Sample Output
17
Hint
#include#include #include #include #include using namespace std;#define int long longint n, m;struct Par{ int l, p, s;}a[105];bool operator < (Par a, Par b){ return a.s < b.s;}int dp[105][16005];deque q;inline int cacl(int x, int y){ return dp[x-1][y] - a[x].p * y;}signed main(){ while(scanf("%lld%lld", &n, &m) != EOF) //cin >> n >> m; { for(register int i = 1 ; i <= m ; i ++) { scanf("%lld%lld%lld", &a[i].l, &a[i].p, &a[i].s); } sort(a + 1, a + 1 +m); for(register int i = 1 ; i <= m ; i ++) { for(register int k = max((int)0, a[i].s - a[i].l) ; k <= a[i].s - 1 ; k ++) { while(!q.empty() && cacl(i, q.back()) <= cacl(i, k)) q.pop_back(); q.push_back(k); } for(register int j = 1 ; j <= n ; j ++) { dp[i][j] = max(dp[i-1][j], dp[i][j-1]); if(j >= a[i].s) { while(!q.empty() && q.front() < j - a[i].l) q.pop_front(); if(!q.empty()) dp[i][j] = max(dp[i][j], cacl(i, q.front()) + a[i].p * j); } } } cout << dp[m][n] << endl; } return 0;}
来个复杂点的:
SCOI2010 股票交易
提交地址 :
题目描述
最近lxhgww又迷上了投资股票,通过一段时间的观察和学习,他总结出了股票行情的一些规律。
通过一段时间的观察,lxhgww预测到了未来T天内某只股票的走势,第i天的股票买入价为每股APi,第i天的股票卖出价为每股BPi(数据保证对于每个i,都有APi>=BPi),但是每天不能无限制地交易,于是股票交易所规定第i天的一次买入至多只能购买ASi股,一次卖出至多只能卖出BSi股。
另外,股票交易所还制定了两个规定。为了避免大家疯狂交易,股票交易所规定在两次交易(某一天的买入或者卖出均算是一次交易)之间,至少要间隔W天,也就是说如果在第i天发生了交易,那么从第i+1天到第i+W天,均不能发生交易。同时,为了避免垄断,股票交易所还规定在任何时间,一个人的手里的股票数不能超过MaxP。
在第1天之前,lxhgww手里有一大笔钱(可以认为钱的数目无限),但是没有任何股票,当然,T天以后,lxhgww想要赚到最多的钱,聪明的程序员们,你们能帮助他吗?
输入输出格式
输入格式:
输入数据第一行包括3个整数,分别是T,MaxP,W。
接下来T行,第i行代表第i-1天的股票走势,每行4个整数,分别表示APi,BPi,ASi,BSi。
输出格式:
输出数据为一行,包括1个数字,表示lxhgww能赚到的最多的钱数。
输入输出样例
5 2 02 1 1 12 1 1 13 2 1 14 3 1 15 4 1 1
3
说明
对于30%的数据,0<=W<T<=50,1<=MaxP<=50
对于50%的数据,0<=W<T<=2000,1<=MaxP<=50
对于100%的数据,0<=W<T<=2000,1<=MaxP<=2000
对于所有的数据,1<=BPi<=APi<=1000,1<=ASi,BSi<=MaxP
设dp[i][j]为第i天拥有j个股票的最大收益;
则dp[i] [j] = dp[i-1][j] 这一天不买、卖股票;
dp[i] [j] = max( dp[i-w-1] [k] + bp[i] * ( j - k) ) , 这是卖出股票, 满足j - k <= bs[i] ;
同理:dp[i] [j] = max( dp[i-w-1] [k] -ap[i] * (k - j) ) 这是买入股票, 满足k - j <= as[i];
然后上面两个式子可以用单调队列优化,具体看代码;
//By zZhBr#include#include #include #include #include using namespace std;#define maxn 2010#define int long longint t, p, w;int ap[maxn], bp[maxn], as[maxn], bs[maxn];int dp[maxn][maxn];deque q;inline int calc1(int i, int j){ return dp[i-w-1][j] + bp[i] * j;}inline int calc2(int i, int j){ return dp[i-w-1][j] + ap[i] * j;}signed main(){ memset(dp, 0xcf, sizeof dp); cin >> t >> p >> w; for(register int i = 1 ; i <= t ; i ++) { scanf("%lld%lld%lld%lld", &ap[i], &bp[i], &as[i], &bs[i]); } dp[0][0] = 0; for(register int i = 1 ; i <= t ; i ++) { for(register int j = 0 ; j <= as[i] ; j ++) dp[i][j] = -ap[i] * j; for(register int j = p ; j >= 0 ; j --) { dp[i][j] = max(dp[i][j], dp[i-1][j]); } if(i - w - 1 >= 0) { q.clear(); for(register int j = p ; j >= 0 ; j --) { if(1)//卖出 { while(!q.empty() && calc1(i, q.back()) <= calc1(i, j)) q.pop_back(); q.push_back(j); while(!q.empty() && - j + q.front() > bs[i]) q.pop_front(); //dp[i][j] = max(dp[i][j], dp[i-w-1][k] + bp[i] * (k - j)); dp[i][j] = max(dp[i][j], calc1(i, q.front()) - bp[i] * j); } } q.clear(); for(register int j = 0 ; j <= p ; j ++) { if(1)//买入 { while(!q.empty() && calc2(i, q.back()) <= calc2(i, j)) q.pop_back(); q.push_back(j); while(!q.empty() && j - q.front() > as[i]) q.pop_front(); //dp[i][j] = max(dp[i][j], dp[i-w-1][k] - ap[i] * (j - k)); dp[i][j] = max(dp[i][j], calc2(i, q.front()) - ap[i] * j); } } } } int ans = 0; for(register int i = 0 ; i <= p ; i ++) { ans = max(ans, dp[t][i]); } cout << ans << endl; return 0; }