#include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; bool rcmp(int a, int b) { return a>b; } typedef long long LL; class mypcmp { public: bool operator()(const int& a, const int& b) { return a=0) v=max(v, dp[i-1][k][0]+1); if (dp[i-1][k][1]>=0) v=max(v, dp[i-1][k][1]+1); } else if (ib[i]=='+') { if (dp[i-1][k][0]>=0) v=max(v, dp[i-1][k][0]+1); if (dp[i-1][k][1]>=0) v=max(v, dp[i-1][k][1]+1); } else { if (dp[i-1][k][0]>=0) v=max(v, dp[i-1][k][0]-1); if (dp[i-1][k][1]>=0) v=max(v, dp[i-1][k][1]-1); } dp[i][k][0]=v; // (k, 1) v=-1; if (ib[i]=='?') { if (k && dp[i-1][k-1][0]>=0) v=max(v, dp[i-1][k-1][0]+1); if (dp[i-1][k][1]>=0) v=max(v, dp[i-1][k][1]+1); } else if (ib[i]=='+') { if (k && dp[i-1][k-1][0]>=0) v=max(v, dp[i-1][k-1][0]-1); if (dp[i-1][k][1]>=0) v=max(v, dp[i-1][k][1]-1); } else { if (k && dp[i-1][k-1][0]>=0) v=max(v, dp[i-1][k-1][0]+1); if (dp[i-1][k][1]>=0) v=max(v, dp[i-1][k][1]+1); } dp[i][k][1]=v; } } for (k=0; k<=20; k++) if (dp[n-1][k][0]>=0||dp[n-1][k][1]>=0) break; printf("%d\n", k); return 0; }