旅行Ⅱ题解_牛客博客

做法1：AC
数据范围较小，考虑状压dp， $cost[i]$ 表示构成集合i的最小花费，用二进制状压表示。所以我们考虑先枚举集合，再枚举集合外的点， $O(n)$ 去验证这个点能否加入这个集合。总的时间复杂度为 $O(n^2*2^n)$ ，空间复杂度为 $O(2^n+m)$ 。

class Solution {
public:
    int Travel(int N, int V, int* A, int ALen, vector<Point>& List) {
        // write code here
        typedef long long ll;
        vector<int>v[N+1];
        vector<ll> cost;
        cost.resize(1<<N+2);
        const ll inf = 1e18;
        for(auto i:List) v[i.y].push_back(i.x);
        for(int i=1;i<1<<N;i++) cost[i]=inf;
        for(int i=0;i<(1<<N);i++) {//枚举集合
            if(cost[i]==inf) continue;
            for(int j=1;j<=N;j++) {
                if(!(i&(1<<(j-1)))) {//枚举不在集合里面的
                    int fg=0;
                    for(auto k:v[j])//看是否被限制
                        if(!(i&(1<<(k-1)))) fg=1;
                    if(fg) continue;
                    cost[i|(1<<(j-1))]=cost[i]+A[j-1];//更新ans
                }
            }
        }
        int ans=0;
        for(int i=0;i<(1<<N);i++) 
            if(V>=cost[i])  {
                bitset<21>b(i);
                int sum=b.count();
                ans=max(ans,sum);
            }
        return ans;
    }
};

做法2：(TLE)
直接 $n!$ 枚举去城市的顺序，然后挨着判断是否可行，时间复杂度 $O(n!*n^2)$ ，空间复杂度为 $O(n+m)$ 。

/**
 * struct Point {
 *    int x;
 *    int y;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param N int整型 N
     * @param V int整型 V
     * @param A int整型一维数组 A
     * @param ALen int A数组长度
     * @param List Point类vector List
     * @return int整型
     */
    int Travel(int N, int V, int* A, int ALen, vector<Point>& List) {
        // write code here
        int b[N+1],vis[N+1];
        vector<int>v[N+1];
        for(auto i:List) v[i.y].push_back(i.x);
        for(int i=1;i<=N;i++) b[i]=i;
        int ans=0;
        do{
            int sum=0;int hav=V;
            memset(vis,0,sizeof vis);
            for(int i=1;i<=N;i++) {
                int id=b[i],fg=0;
                for(auto j:v[id])
                    if(!vis[j]) fg=1;
                if(fg) break;
                if(hav>=A[id-1]) {
                    sum++;
                    hav-=A[id-1];
                }else break;
                vis[id]=1;
            }
            ans=max(ans,sum);
        }while(next_permutation(b+1,b+1+N));
        return ans;
    }
};