题目描述

blablabla

样例

blablabla

算法1

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

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

include[HTML_REMOVED]

include[HTML_REMOVED]

include[HTML_REMOVED]

include[HTML_REMOVED]

include[HTML_REMOVED]

include[HTML_REMOVED]

include[HTML_REMOVED]

include[HTML_REMOVED]

//#define int long long

define endl “\n”

using namespace std;
typedef pair[HTML_REMOVED] 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<[HTML_REMOVED]>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;
}

}

算法2

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

blablabla

时间复杂度

参考文献

C++ 代码

blablabla