题目描述

blablabla

样例

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cmath>
#include<queue>
#include<map>
#include<unordered_map>
//#define int long long
#define endl "\n"
using namespace std;
typedef pair<int,int> PII;
const int N=15,mod=1e9+7,M=N*2;
int n,m,k,x;
int a[N];
int b[N];
string s[N];
int ans;
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin>>t;
    while(t--){
        cin>>n;
        int f[1<<n];
        int t[1<<n];//先预处理
        int pre[1<<n];
        memset(f,0x3f,sizeof f);//f输出答案
        memset(pre,0,sizeof pre);
        f[0]=0;
        memset(t,0,sizeof t);//g代表当前的时间是多少
        for(int i=0;i<n;i++){
            cin>>s[i]>>a[i]>>b[i];//学科 截至日期 完成时间
        }

        for(int i=1;i<(1<<n);i++){//枚举集合
            for(int j=0;j<n;j++){
                if(i>>j&1){//枚举最后一个的意思
                    //先算时间
                    t[i]+=b[j];//算总时间宝宝
                }
            }
        }

        for(int i=0;i<(1<<n);i++){//枚举集合
            for(int j=0;j<n;j++){
                if((i>>j&1)==0){//枚举最后一个的意思
                    //先算时间
                    int nxt=i|(1<<j);//下一个集合
                    int val=f[i]+max(0,t[i]+b[j]-a[j]);
                    if(f[nxt]>val){
                        f[nxt]=val;//不用扣分了意思就是
                        pre[nxt]=j;
                    }
                }
            }
        }
        int u=(1<<n)-1;
        cout<<f[u]<<endl;
        //for(int i=1;i<=u;i++)cout<<pre[i]<<" "<<endl;
        vector<string> ans;

       while(u!=0){
            ans.push_back(s[pre[u]]);
            u=u^(1<<pre[u]);
            //cout<<u<<endl;
        }
        reverse(ans.begin(),ans.end());
        for(auto x:ans)cout<<x<<endl;
    }
}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla