巨人网络，9.23笔试AK代码，C++
两道题其实都挺简单的，但是都是在奇怪的地方可能引起歧义或者卡住。
第一题的意思，被消除的部分在初始是“连续的区域”就叫连续消除，不一定需要在时间上同一轮或者连续。
我是用了一个栈来模拟这个过程，然后记录下来被消除的初始位置，然后再扫描一遍找连续区域的最大值。
#include<bits/stdc++.h>
using namespace std;
struct node
{
int pos; //初始位置
char c; //字符，‘1’或‘0’
node(int p,char c1){
pos=p;c=c1;
}
};
int getLongest(string s){
stack<node> sta;
int leng=s.size();
vector<bool> canmove(leng,0);
for(int i=0;i<leng;i++){
if(s[i]=='1'){
sta.push(node(i,'1'));
}
else{
if(!sta.empty()&&sta.top().c=='1'){
canmove[sta.top().pos]=1;
canmove[i]=1;
sta.pop();
}
else{
sta.push(node(i,'0'));
}
}
}
int res=0;
int i=0;
while(i<leng){
while(i<leng&&!canmove[i])i++;
int templeng=0;
while(i<leng&&canmove[i]){
templeng++;i++;
}
if(templeng>res)res=templeng;
}
return res;
}
int main(){
string s;
cin>>s;
cout<<getLongest(s)<<endl;
} 第二题是很简单的动态规划，dp[i][j]=max(dp[i+1][j],dp[i][j+1])+girft[i][j]，处理一下边界即可，主要是他这个输入太坑爹了，他输入的就是“[[1,2,3],[1,3,1],[4,5,6]]”带括号和逗号一块输入的，要手动分离开开， 我是用的一个字符变量和一个整形变量接收输入，根据字符变量是逗号或者左括号判断下一个是数字，还是换行，还是结束
#include<bits/stdc++.h>
using namespace std;
int result(vector<vector<int>> girft){
int xleng=girft.size();
int yleng=girft[0].size();
vector<vector<int>> dp(xleng,vector<int>(yleng));
dp[xleng-1][yleng-1]=girft[xleng-1][yleng-1];
for(int i=xleng-2;i>-1;i--)dp[i][yleng-1]=dp[i+1][yleng-1]+girft[i][yleng-1];
for(int i=yleng-2;i>-1;i--)dp[xleng-1][i]=dp[xleng-1][i+1]+girft[xleng-1][i];
for(int i=xleng-2;i>-1;i--){
for(int j=yleng-2;j>-1;j--){
dp[i][j]=girft[i][j]+max(dp[i+1][j],dp[i][j+1]);
}
}
return dp[0][0];
}
int main(){
char c;
vector<vector<int>> get;
cin>>c;
while(1){
cin>>c;
int num;
vector<int> temp;
while(c!=']'){
cin>>num>>c;
temp.push_back(num);
}
get.push_back(temp);
cin>>c;
if(c==']')break;
}
cout<<result(get)<<endl;
} 
微软公司福利 57人发布
