例题6-3 Matrix Chain Multiplication ,Uva 442

这个题思路没有任何问题,但还是做了近三个小时,其中2个多小时调试例题6-3 Matrix Chain Multiplication ,Uva 442

得到的经验有以下几点:

  1. 一定学会调试,掌握输出中间量的技巧,加强gdb调试的学习
  2. 有时候代码不对,得到的结果却是对的(之后总结以下常见错误)
  3. 能用结构体,就别用数组,容易出错(暂时还不知道为什么)=>现在知道申请的数组空间在运行期间被释放,除非用malloc去申请数组
  4. 代码要规范,空格该有就要有
  5. 有些不规范表达式,不同编译器出现不同结果,注意应避免使用这类语句

像这道题主要坑在了第三点上,以后要注意避免

以下是AC代码

第一次完成时间(大于2小时)

#include <cstdio>
#include <stack>
#include <cstring>
#include <cctype>
const int MAXN=+;
using namespace std;
char exps[MAXN];
struct Matrix {
int a, b;
Matrix(int a = ,int b = ):a(a), b(b) {}
}m[];
stack<Matrix> s;
int main(){
#ifdef DEBUG
freopen("6.3.in","r",stdin);
#endif
int n;
scanf("%d\r",&n);
for(int i=;i<n;i++){
char s0[];
char c;
scanf("%c ",&c);
s0[]=c;
scanf("%d %d\r\n",&m[s0[] -'A'].a, &m[s0[] -'A'].b);
//printf("%c %d %d\r\n",s0[0] , m[s0[0] -'A'].a , m[s0[0]-'A'].b);
}
while(scanf("%s",exps)==){
int sum=;
int len=strlen(exps);
int ok=;
for(int i=;i<len;i++){
if(isalpha(exps[i])){
s.push(m[exps[i]-'A']);
// printf("push %d %d \n",m[exps[i]-'A'].a,m[exps[i]-'A'].b);
}
else if(exps[i]==')'){
Matrix m2 = s.top(); s.pop();
// printf("pop %d %d \n", m2.a, m2.b);
Matrix m1 = s.top(); s.pop();
// printf("pop %d %d \n", m1.a, m1.b);
if(m1.b != m2.a){ok=;break;}
sum+= m1.a * m1.b * m2.b;
s.push(Matrix(m1.a, m2.b));
// printf("push %d %d \n",m1.a, m2.b,);
}
}
if(ok)printf("%d\n",sum);
else printf("error\n");
}
return ;
}

第二次练习代码(完成时间约1小时)

 //UVa 442,Matrix Chain Multiplication
//Example:6-3
//Author:wzh
//Date: 2016.8.26
//Version 2 #include <cstdio>
#include <cstring>
#include <cctype>
#include <stack>
#include <cstdlib>
using namespace std;
#define maxn 30
int s[maxn][];
char buf[];
int main(){
#ifdef D
freopen("442.in","r",stdin);
#endif
int n;
scanf("%d ",&n);
for(int i=;i<n;i++){
char c;int a,b;
scanf("%c",&c);
scanf("%d%d ",&s[c-'A'][],&s[c-'A'][]);
//printf("%c %d %d\n",c,s[c-'A'][0],s[c-'A'][1]);
} while(fgets(buf,,stdin)){
int len=strlen(buf);
stack<int*> sk;
int sum=;
int ok=;
for(int i=;i<len;i++){
if(buf[i]==')'){
int *a,*b,*c;
b=sk.top();sk.pop();
//printf("pop%d %d\n",b[0],b[1]);
a=sk.top();sk.pop();
// printf("pop%d %d\n",a[0],a[1]);
if(a[]==b[]){
sum+=(a[]*a[]*b[]);
c=(int*)malloc(sizeof(int)*);
c[]=a[];
c[]=b[];
sk.push(c);
// printf("push*%d %d\n",c[0],c[1]);
}
else{
ok=;
break;
}
}
else if(isalpha(buf[i])){
sk.push(s[buf[i]-'A']);
//printf("push%d %d\n",s[buf[i]-'A'][0],s[buf[i]-'A'][1]);
}
}
if(ok)printf("%d\n",sum);
else printf("error\n");
}
return ;
}
上一篇:POJ 3494 Largest Submatrix of All 1’s 单调队列||单调栈


下一篇:POJ3494Largest Submatrix of All 1’s[单调栈]