poj2531求助
  • 板块题目总版
  • 楼主__2304__
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/7/2 09:59
  • 上次更新2024/7/2 13:03:42
查看原帖
poj2531求助
719611
__2304__楼主2024/7/2 09:59

原题

为什么剪枝之后还是TLE(我是枚举将A集合当中的 电脑移到B集合中)

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int MAXN=25;
int n,c[MAXN][MAXN],ans;
vector<int> A,B;
void dfs(int x){
    int sum=0;
    for(int i=0;i<A.size();i++) for(int j=0;j<B.size();j++) sum+=c[A[i]][B[j]];
    if(sum>=ans) ans=sum;
    else return;
    for(int i=x;i<A.size();i++){
        B.push_back(A[i]);
        A.erase(A.begin()+i);
        dfs(x);
        A.push_back(B[B.size()-1]);
        B.pop_back();
        sort(A.begin(),A.end());
    }
    return;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>c[i][j];
    for(int i=1;i<=n;i++) A.push_back(i);
    dfs(0);
    cout<<ans;
    system("pause");
    return 0;
}
2024/7/2 09:59
加载中...