原题通道：ZOJ1246
大概思路：用深搜的思想+数组的加减去模拟括号的进入和弹出。并且用数组的加减操作模拟数据项的加减操作，具体题意看了下面的输入输出应该能理解。
直接看输出输入
输入
Sample Input
2
BEGIN
LOOP n
OP 4
LOOP 3
LOOP n
OP 1
END
OP 2
END
OP 1
END
OP 17
END
BEGIN
OP 1997 LOOP n LOOP n OP 1 END END
END
输出
Program #1
Runtime = 3*n^2+11*n+17
Program #2
Runtime = n^2+1997
2表示有两个测试样例，其中BEGIN表示每个测试样例的开始。看下第一个样例的情况。
LOOP n -> n×( )
OP 4 -> n×( 4 + )
LOOP 3 -> n×( 4 + 3×( ) )
LOOP n -> n×( 4 + 3×( n×( ) ) )
OP 1 -> n×( 4 + 3×( n×( 1 ) ) )
END OP 2 -> n×( 4 + 3×( n×( 1 ) + 2 ) )
END OP 1 -> n×( 4 + 3×( n×( 1 ) + 2 ) + 1 )
END OP 17 -> n×( 4 + 3×( n×( 1 ) + 2 ) + 1 ) + 17
所以最后的结果就是：n×( 4 + 3n + 6 + 1 ) + 17 = 3n^2 + 11n + 17
就是，LOOP表示进一个括号，OP表示在括号里面进行加减，END表示跳出一个括号
每个LOOP对应一个END，BEGIN对应一个END
看了输入输出基本上就差不多已经理解题目了，然后要注意，n×( n×(n×( )))，也就是
2
BEGIN
LOOP 1
LOOP 1
LOOP 1
END
END
END
END
BEGIN
END
这两个例子的结果都是0
代码解析
- 因为
OP和LOOP后面的可以是n，也可以是1~9，也可以是>10，所以我用string接收后面的参数，如果第一个字符不是n，则转化为int型
int getInt(string s){ //用来把一个字符串转化为int型数据
int num = 0,ff = 1;
for(long i = s.size() - 1; i>=0; i--){
num += (s[i]-'0')*ff;
ff *= 10;
}
return num;
}
- 数组相乘和相加。
int temp[] = {1,2,6,4……}，这个数组表示1+2n+6n^2+4n^3，也就是用数组下标表示幂次方，数组元素表示对应的系数。所以用以下两个函数表示一个数（n或者一个数）乘以一个数组和两个数组相加。
void mul(string w,int (&temp)[N]){ //一个数乘以一个数组
if(w[0]>='0'&&w[0]<='9'){
int kw = getInt(w);
for(int i=0; i<N; i++) temp[i] *= kw;
}else{
for(int i=N-1; i>0; i--)
temp[i] = temp[i-1];
temp[0] = 0;
}
}
void add(int (&a)[N],int (&temp)[N]){ //两个数组相加
for(int i=0; i<N; i++)
temp[i] = temp[i] + a[i];
}
- 用dfs表示递进和，如果是OP操作，则进行加操作。如果是LOOP操作，则先
dfs()取得递归层的结果集，因为是引用操作，所以dfs(k)之后，k里面已经有数据了，所以可以执行mul(ch,k)操作，执行操作之后继续在本dfs()中，直到遇到END则退出到上一个dfs()中。用一点深搜的思想来模拟括号的进入和弹出
void dfs(int (&temp)[N]){
string ch;
while(cin>>str&&str!="END"){
cin>>ch;
if(str=="OP"){
if(ch[0]>='0'&&ch[0]<='9'){ //下标0处直接加
int cot = getInt(ch);
temp[0] += cot;
}
else temp[1] += 1; //如果是OP n，则加在下标为1的位置
}else if(str=="LOOP"){
int k[N] = {0};
dfs(k);
mul(ch,k);
add(k,temp);
}
}
}
完整代码如下
#include <iostream>
#include <string>
#define N 21
using namespace std;
string str;
int getInt(string s){
int num = 0,ff = 1;
for(long i = s.size() - 1; i>=0; i--){
num += (s[i]-'0')*ff;
ff *= 10;
}
return num;
}
void mul(string w,int (&temp)[N]){
if(w[0]>='0'&&w[0]<='9'){
int kw = getInt(w);
for(int i=0; i<N; i++) temp[i] *= kw;
}else{
for(int i=N-1; i>0; i--)
temp[i] = temp[i-1];
temp[0] = 0;
}
}
void add(int (&a)[N],int (&temp)[N]){
for(int i=0; i<N; i++)
temp[i] = temp[i] + a[i];
}
void dfs(int (&temp)[N]){
string ch;
while(cin>>str&&str!="END"){
cin>>ch;
if(str=="OP"){
if(ch[0]>='0'&&ch[0]<='9'){
int cot = getInt(ch);
temp[0] += cot;
}
else temp[1] += 1;
}else if(str=="LOOP"){
int k[N] = {0};
dfs(k);
mul(ch,k);
add(k,temp);
}
}
}
int main(int argc, const char * argv[]) {
int T,flag;
cin>>T;
for(int l = 1; l<=T; l++){
cin>>str;
int temp[N] = {0}; //初始化数据
dfs(temp); //递归得到结果集
cout<<"Program #"<<l<<endl<<"Runtime = ";
flag = 0;
for(int i=N-1; i>=0; i--) //遍历结果集并输出
if(temp[i]!=0){
if(flag) cout<<"+";
else flag = 1;
if((i!=0&&temp[i]!=1) || i==0) cout<<temp[i];
if(i>0&&temp[i]!=1) cout<<"*n";
else if(i>0&&temp[i]==1) cout<<"n";
if(i>1) cout<<"^"<<i;
}
if(flag==0) cout<<"0"; //如果不存在，则输出0
cout<<endl<<endl;
}
return 0;
}
看网上好像没有这题的题解，顺手写一个……
