DFS策略：对于当前状态，枚举下一个选哪个(i)，如果当前耗时已经超过i的死亡线，ans就累积
然后可以记忆化当前状态标记为true 之后扫到这儿就return
代码不是A的。。和几份题解都对拍了半天没找出问题 如果能指出错误的话请评论
#include<bits/stdc++.h> #define N 17 #define INF 0x3f3f3f3f using namespace std; int T,n,a[N],b[N],ans; bool vis[1<<N]; struct Data { string name; int dead,tim; }sub[N]; inline int count(int x) { int num=0; while(x) { if(x&1) num++; x>>=1; } return num; } void dfs(int state,int day,int reduce) { if(state==(1<<n)-1) { if(ans>reduce) { ans=reduce; for(int i=1;i<=n;i++) b[i]=a[i]; } return; } if(vis[state]) return; vis[state]=true; for(int i=1;i<=n;i++) { if(state&(1<<(i-1))) continue; int num=count(state)+1; //第几个选的 a[num]=i; if(day+sub[i].tim>sub[i].dead) //如果加上i的天数已经超过i的死亡线 dfs(state|(1<<(i-1)),day+sub[i].tim,reduce+day+sub[i].tim-sub[i].dead); else dfs(state|(1<<(i-1)),day+sub[i].tim,reduce); a[num]=0; } } int main() { cin>>T; while(T--) { cin>>n; for(int i=1;i<=n;i++) { cin>>sub[i].name>>sub[i].dead>>sub[i].tim; } ans=INF; memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); memset(vis,false,sizeof(vis)); dfs(0,0,0); cout<<ans<<endl; for(int i=1;i<=n;i++) cout<<sub[b[i]].name<<endl; } return 0; }转载于:https://www.cnblogs.com/Patrickpwq/articles/9811400.html
相关资源：各显卡算力对照表！