题解 | #[NOIP2001]装箱问题#

分两种情况进行dp。

用大根堆和小根堆分别存一次数据；

然后输出两种情况下较小的dp。

#include<iostream>

#include<cstring>

#include<queue>

using namespace std;

int V,n;

int a[31];

int dp1[31];

int dp2[31];

priority_queue<int> cml;//建立大根堆

priority_queue<int,vector<int>,greater<int> > wsq;//建立小根堆

int main()

{

cin>>V>>n;

int x;

for(int i=1;i<=n;i++){

cin>>x;

cml.push(x);//存进大根堆

wsq.push(x);//存进小根堆

}

dp1[0]=V;

for(int i=1;i<=n;i++){

if(cml.top()>dp1[i-1]){

dp1[i]=dp1[i-1];

cml.pop();

continue;

}

dp1[i]=dp1[i-1]-cml.top();

cml.pop();

}

dp2[0]=V;

for(int i=1;i<=n;i++){

if(wsq.top()>dp2[i-1]){

dp2[i]=dp2[i-1];

wsq.pop();

continue;

}

dp2[i]=dp2[i-1]-wsq.top();

wsq.pop();

}

cout<<min(dp1[n],dp2[n]);

return 0;

}