首页 > 代码库 > hdu 4699
hdu 4699
两个栈,光标前的元素一个栈,光标后的元素一个栈
sum[i]记录从1~i个元素之和,动态规划的状态方程是 dp[i] = max( dp[i-1], sum[i] ),dp[i]记录前i个元素的最大和值。
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<algorithm> #include<vector> #include<stack> using namespace std; const int Inf = 1e9+50; const int maxn = 1e6+50; int sum[maxn]; int dp[maxn]; stack<int> pre; stack<int> tail; int main() { int m, x; char ch[10]; while(~scanf("%d", &m)) { int cursor = 0; dp[0] = -Inf; sum[0] = 0; while( !pre.empty() ) pre.pop(); while( !tail.empty() ) tail.pop(); while(m --) { scanf("%s", ch); if( ch[0] == 'I' ){ scanf("%d", &x); pre.push(x); cursor ++; sum[cursor] = sum[cursor-1] + x; dp[cursor] = max(dp[cursor-1], sum[cursor]); } else if( ch[0] == 'D' ){ if(cursor == 0) continue; cursor --; pre.pop(); } else if( ch[0] == 'L' ){ if(cursor == 0) continue; cursor --; tail.push(pre.top()); pre.pop(); } else if( ch[0] == 'R' ){ if(tail.empty()) continue; cursor ++; pre.push(tail.top()); tail.pop(); sum[cursor] = sum[cursor-1] + pre.top(); dp[cursor] = max(dp[cursor-1], sum[cursor]); } else { scanf("%d", &x); printf("%d\n", dp[x]); } } } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。