Ecole Polytechnique Contest 解题报告

hello kity

期待您的批阅，由于写解题报告时不一定考虑的很周到，所以如果您有什么不懂的地方，请您留言，然而一天之内我肯定会看见您信息，再对代码注释详细，让您更好的阅读

分类

POJ （2246） Matrix Chain Multiplication

题目分析：简单的后缀表达式，把每个表达式存放在string 变量里，然后从前到后遍历一边，当遇到'('直接存放在记录运算符的栈里，如果是字母就把这个字母对应的节点存放在，记录运算节点的栈里！最后当遇到 ')' 如果记录运算符号的栈里为空，就说明括号不对称！所以得出error！否则把栈里的'('的出栈！然后把记录运算节点的栈里取出两个运算节点！对这两个节点进行判断,是否满足矩阵运算规则，如果不满足，判错！满足的话记录下他们的乘积！并且将两个节点合并成一个节点存放回在记录运算节点的栈里！

算法详细过程就是这样下面是我的代码如有改正的地方请您留言谢谢

#include<iostream>
#include<stdio.h>
#include<stack>
#include<cstring>
using namespace std;
 
struct node{
    int x,y;
}s[30];
int n;
void input(){
    char c;
    while(n--){
        cin>>c;
        int t=c-'A';
        cin>>s[t].x>>s[t].y;
    }
}
 
int cal(string str){
    int i,k=str.length(),ans=0;
    struct node a,b;
    stack<char>sn;
    stack<struct node>st;
    for(i=0;i<k;i++){
        if(str[i]=='(')
            sn.push(str[i]);    
        else if(str[i]>='A'&&str[i]<='Z')
            st.push(s[str[i]-'A']);
        else{
            if(sn.empty())
                return -1;
            sn.pop();
            b=st.top();
            st.pop();
            a=st.top();
            st.pop();
            if(a.y!=b.x)
                return -1;
            ans+=a.x*b.x*b.y;
            a.y=b.y;
            st.push(a);
             
        }
             
    }
    return ans;
}
 
int main(){
    int sum;
    string str;
    cin>>n;
    input();
    while(cin>>str){
        sum=cal(str);
        if(sum==-1)
            printf("error\n");
        else
            printf("%d\n",sum);
    }
    return 0;
}

POJ Wooden Sticks

题目分析：就是让你求一个坐标数组里，满足x,y同时递增的序列个数！

拿到题目我就想到贪心，但是一直没得到很好的证明，所以一直迟迟不敢去尝试，毕竟也是比赛，呵呵，后来有人说贪心过，突然觉得自己也许会考虑的复杂了！其实题目也没有什么最优解选择方案，只是简简单单的 x,y同时递增的序列个数。

现在就贴一下我的代码如果您有对本题有更好的思路希望您能给我批阅！{^_^}

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<cstring>
using namespace std;
 
struct node{
    int x,y;
}s[10000];
 
int vs[10000];
 
int cmp(struct node a,struct node b){
    if(a.x!=b.x)
        return a.x<b.x;
    else
        return a.y<b.y;
}
 
int main(){
    int cas,n,i,ans,j,t;
    cin>>cas;
    while(cas--){
        cin>>n;
        memset(vs,0,sizeof(vs));
        ans=0;
        for(i=1;i<=n;i++){
            cin>>s[i].x>>s[i].y;
        }
        sort(s+1,s+n+1,cmp);
        for(i=1;i<=n;i++){
            if(!vs[i]){
                t=s[i].y;
                ans++;
                for(j=i+1;j<=n;j++){
                    if(s[j].y>=t&&vs[j]==0){
                        t=s[j].y;
                        vs[j]=1;
                    }
                }
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}