１．给两个数组a,b和一个数组c，问c是否能由a,b按顺序合并而成
AC代码：
void solution(){
int N;
cin>>N;
std::vector<string> res;
while(N--){
int a_size,b_size;
cin>>a_size>>b_size;
int c_size = a_size+b_size;
vector<int> a,b,c;
while(a_size--){
int temp;
cin>>temp;
a.emplace_back(temp);
}
while(b_size--){
int temp;
cin>>temp;
b.emplace_back(temp);
}
while(c_size--){
int temp;
cin>>temp;
c.emplace_back(temp);
}
int p_a = 0;
int p_b = 0;
int p_c = 0;
if(back(p_a,p_b,p_c,a,b,c))
res.emplace_back("possible");
else
res.emplace_back("not possible");
}
for(auto& s:res){
std::cout<<s<<std::endl;
}
}
bool back(int p_a, int p_b, int p_c, vector<int>& a,vector<int>& b,vector<int>& c){
if(p_c>=a.size()+b.size())
return true;
if(p_a<a.size()&&a[p_a] == c[p_c]){
if(back(p_a+1,p_b,p_c+1,a,b,c))
return true;
}
if(p_b<b.size()&&b[p_b] == c[p_c]){
return back(p_a,p_b+1,p_c+1,a,b,c);
}
return false;
} ２．给定一个数组，数组中的每个数字只能和连续相邻的数字组队，且队伍实力由木桶效应决定，即队伍里最小的数代表队伍的实力，求每个队伍人数为i(1<=i<=nums,size())时的实力最强队伍的实力．
30%代码，动态规划，每次求以nums[j]为起点队伍人数为i的队伍的实力时都是根据人数为i-1时转移而来的，dp[j] = std::min(dp[j],nums[j+k-1])，不知道为什么只能过30%，求解答
void solution2(){
int n;
cin>>n;
std::vector<long int> res;
vector<long int> nums;
while(n--){
int temp;
cin>>temp;
nums.emplace_back(temp);
}
std::vector<long int> dp(nums.size(),INT_MAX);
for (int i = 1; i <= nums.size(); ++i) {
long int max_num = INT_MIN;
for (int j = 0; j < nums.size()-i+1; ++j) {
dp[j] = std::min(dp[j],nums[j+i-1]);
max_num = std::max(max_num,dp[j]);
}
res.emplace_back(max_num);
}
for(int i=0;i<res.size()-1;i++){
std::cout<<res[i]<<" ";
}
std::cout<<res.back();
} 
全部评论
(1) 回帖