修吗王D04T2
2026-02-09 17:36:36
发布于：北京
8阅读
0回复
0点赞
#include<bits/stdc++.h>
using namespace std;
int n,t;
struct node{
int x,t;
friend bool operator <(node x,node y){
if(x.t==y.t)return x.x<y.x;
else return x.t<y.t;
}
};
node _min(node x,node y){
if(x<y){
return x;
}else{
return y;
}
}
node add(node x,int y){
if(x.x+y<=t){
x.x+=y;
}else{
x.t++;
x.x=y;
}
return x;
}
int a[17];
node dp[(1<<17)];
int main(){
cin>>n>>t;
if(n==0){
cout<<0;
return 0;
}
for(int i=0;i<n;i++){
cin>>a[i];
}
for(int i=0;i<=(1<<n);i++){
dp[i].x=1e9;
dp[i].t=1e9;
}
node x;//随时可用
x.x=0;
x.t=1;
dp[0]=x;
for(int i=0;i<(1<<n);i++){
int cnt = __builtin_popcount(i);//记录有多少个1
for(int j=0;j<n;j++){
if(!(i&(1<<j))){
dp[i|(1<<j)]=_min(dp[i|(1<<j)],add(dp[i],a[j]));//a[j]还是a[cnt]
//cout<<bian_erjin(i)<<"->"<<bian_erjin(i|(1<<j))<<" dp["<<dp[i].t<<"->"<<dp[i|(1<<j)].t<<endl;
}
}
}
cout<<dp[(1<<n)-1].t;
return 0;
}
这里空空如也
有帮助，赞一个