有没有大佬帮我改进算法,腾讯这次的第四题,但是超时了

#include <iostream>

using namespace std;

#include<vector>

#include<bitset>

vector<int>res;

vector<vector<int>>path;

// int fun(int a,int b)

// {

// int c;

// c=a^b;

// return c;

// }

int getint(vector<vector<int>>path)

{

int sum = 0;

int n = path.size();

int res1 = 0;

vector<int>r;

for (int i = 0; i < n; i++)

{

int m = path[i].size();

for (int j = 0; j < m; j++)

{

sum = sum ^ path[i][j];

}

res1 += sum;

sum = 0;

}

// for(int k=0;k<n;k++)

// {

// res1+=r[k];

// }

return res1;

}

void backtracking(vector<int>& v, int k, int index, int sum)

{

if (sum == k)

{

vector<int>s;

for (int j = index; j < v.size(); j++)

{

s.push_back(v[j]);

}

path.push_back(s);

int b = getint(path);

//cout<<path.size()<<endl;

path.pop_back();

res.push_back(b);

return;

}

for (int i = index; i < v.size(); i++)

{

vector<int>s;

for (int j = index; j <= i; j++)

{

s.push_back(v[j]);

}

path.push_back(s);

sum = sum + 1;

backtracking(v, k, i + 1, sum);

path.pop_back();

sum = sum - 1;

}

}

int main() {

int n, k;

cin >> n >> k;

vector<int>v;

int a;

for (int i = 0; i < n; i++)

{

cin >> a;

v.push_back(a);

}

backtracking(v, k, 0, 1);

int m = res.size();

int result = 0;

for (int i = 0; i < m; i++)

{

result = max(result, res[i]);

}

cout << result;

}

全部评论
回溯也太暴力了,这个题是动态规划
1 回复
分享
发布于 04-01 10:30 湖北
蹲,我都不晓得抑或是那个,写了个赛博骰子,随机输出整数
点赞 回复
分享
发布于 03-31 22:42 广东
滴滴
校招火热招聘中
官网直投

相关推荐

点赞 收藏 评论
分享
牛客网
牛客企业服务