【例题】Push,Pop,GetMin
手写一个栈
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 using namespace std; 8 const int maxn=1000000; 9 int stack[maxn], m[maxn], top=0, m_top=0;10 int n;11 12 void push(int x) {13 stack[++top]=x;14 int tmp=m[m_top];15 m[++m_top]=min(x, tmp);16 }17 18 void pop() {19 stack[top]=m[m_top]=0;20 --top, --m_top;21 }22 23 int main() {24 int x;25 char ops[3];26 m[0]=0x3f3f3f3f;27 scanf("%d", &n);28 for (int i=1; i<=n; ++i) {29 scanf("%s %d", ops, &x);30 if (ops[0]=='p') push(x);31 else if(ops[0]=='q') pop();32 printf("The current minimum number: %d\n", m[m_top]);33 }34 return 0;35 }
考虑维护一个对顶栈，一开始用STL里的栈过不了
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 using namespace std; 9 const int maxn=1000000+10;10 const int INF=0x3f3f3f3f;11 int f[maxn], sum[maxn];12 //stack A, B;13 int A[maxn], B[maxn], tpA, tpB;14 15 int main() {16 //freopen("a.txt", "r", stdin);17 int n;18 while (~scanf("%d", &n)) {19 char ops[3]; int t;20 sum[0]=0, f[0]=-INF, tpA=0, tpB=0;21 while (n--) {22 scanf("%s", ops);23 if (ops[0]=='I') {24 scanf("%d", &t);25 /*A.push(t);26 int p=A.size();27 sum[p]=sum[p-1]+t;28 f[p]=max(f[p-1], sum[p]);*/29 A[++tpA]=t;30 sum[tpA]=sum[tpA-1]+t;31 f[tpA]=max(f[tpA-1], sum[tpA]);32 }33 if (ops[0]=='D') {34 //A.pop();35 --tpA;36 }37 if (ops[0]=='L') {38 /*if (!A.empty()) {39 int tmp=A.top();40 A.pop();41 B.push(tmp);42 }*/43 if (tpA) {44 int x=A[tpA];45 --tpA;46 B[++tpB]=x;47 }48 }49 if (ops[0]=='R') {50 /*if (!B.empty()) {51 int tmp=B.top();52 B.pop();53 A.push(tmp);54 int p=A.size();55 sum[p]=sum[p-1]+tmp;56 f[p]=max(f[p-1], sum[p]);57 }*/58 if (tpB) {59 int x=B[tpB];60 --tpB;61 A[++tpA]=x;62 sum[tpA]=sum[tpA-1]+x;63 f[tpA]=max(f[tpA-1], sum[tpA]);64 }65 }66 if (ops[0]=='Q') {67 scanf("%d", &t);68 printf("%d\n", f[t]);69 }70 }71 }72 return 0;73 }
【例题】/ 进出栈序列问题
方法一：搜索
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 using namespace std; 9 const int maxn=30;10 int n, cnt=0, kase=0, ans[maxn]; 11 int s[maxn], top=0;12 13 void dfs(int x) {14 if (kase>20) return;15 if (x==n+1) {16 if (++kase>20) return;17 for (int i=1; i<=cnt; ++i)18 printf("%d", ans[i]);19 for (int i=top; i>0; --i)20 printf("%d", s[i]);21 printf("\n");22 return;23 }24 if (top) {25 ans[++cnt]=s[top--]; //出栈 26 dfs(x);27 s[++top]=ans[cnt--];28 }29 s[++top]=x;30 dfs(x+1);31 --top;32 }33 34 int main() {35 cin>>n;36 dfs(1);37 return 0;38 }
方法二：递推
因为不计算具体的序列，只计算方案数
8分代码，需要高精度，我不会。。。
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 using namespace std; 9 const int maxn=60000+10;10 int n;11 long long s[maxn];12 13 14 int main() {15 scanf("%d", &n);16 s[0]=1, s[1]=1, s[2]=2;17 for (int i=3; i<=n; ++i) {18 //考虑1这个数排在最终出栈序列的位置19 for (int j=1; j<=i; ++j)20 s[i]+=s[j-1]*s[i-j]; 21 }22 printf("%lld\n", s[n]);23 return 0;24 }
方法三：dp
放弃。。。
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 using namespace std; 9 const int maxn=60000+10;10 int n;11 long long f[maxn][maxn];12 13 14 int main() {15 scanf("%d", &n);16 f[0][0]=1;17 for (int i=1; i<=n; ++i) {18 for (int j=1; j<=n; ++j) {19 f[i][j]=f[i-1][j]+f[i][j-1];20 }21 }22 printf("%lld\n", f[n][0]);23 return 0;24 }
方法四：数学
Catalan数
单调栈
及时排除不可能的选项，保持策略集合的高度有效性和秩序性
考虑维护一个单调栈，在出栈过程中不断更新答案，可以在an右边添加一个高度为0的矩形，避免栈内有剩余矩形。
#include#include #include #include #include #include #include using namespace std;const int maxn=100000+10;const int INF=0x3f3f3f3f;int n, a[maxn], w[maxn];int s[maxn], p=0;int main() { while (scanf("%d", &n)&&n) { long long ans=0; for (int i=1; i<=n; ++i) scanf("%d", &a[i]); a[n+1]=p=0; for (int i=1; i<=n+1; ++i) { if (a[i]>s[p]) { s[++p]=a[i], w[p]=1; } else { int width=0; while (s[p]>a[i]) { width+=w[p]; ans=max(ans, (long long)width*s[p]); --p; } s[++p]=a[i], w[p]=width+1; } } printf("%lld\n", ans); } return 0;}