将桶按容积大小从小到大排序，令 \(f_{i,j}\) 表示前 \(i\) 个桶能否量出 \(j\) 夸脱，如果可以就用 vector 存储最优方案。
先枚举桶的种类再枚举夸脱数，转移看似只有两种：之前有或没有用过 \(i\) 号桶，新用一次 \(i\) 号桶。但这样是错误的，可能存在中间状态最优解长度较长的情况。具体例子可以看代码末尾。
所以我们还需要额外枚举用桶的次数而不是一次一次用，这样最优情况就不会被覆盖了。时间复杂度 \(O(Q^2\log P)\)。
考虑将桶按容积从大到小排序，令 \(f_{i,j}\) 表示前 \(i\) 个桶能否量出 \(j\) 夸脱，如果可以就令 \(g_{i,j}\) 表示最优方案需要桶的数量，\(used_{i,j}\) 表示最优方案有没有用 \(i\) 号桶。
这样我们就可以一次一次用了，最优解肯定不会被覆盖。
最后再根据记录的信息搜索一遍，\(\require{cancel}\require{enclose}\sout{O(kQ^2P\log P)}\) 跑得飞快，其中 \(k\) 取决于方案长度，很小很小。
#include<bits/stdc++.h>
using namespace std;
#define N 105
#define NN 20005
#define For(i,x,y)for(i=x;i<=(y);i++)
#define Down(i,x,y)for(i=x;i>=(y);i--)
int g[N][NN],c[N];
/*vector<int>h[N][NN];*/
bool used[N][NN],f[N][NN];
vector<int>print(int now,int pos)
{
if(g[pos][now]==1)return{c[pos]};
/*if(!h[pos][now].empty())return h[pos][now];*/
int i,j,k;
vector<int>vec,tmp;
Down(i,pos-1,1)
{
j=now;
while(j>=c[pos])
{
j-=c[pos];
/*cerr<<i<<' '<<j<<' '<<pos<<' '<<now<<' '<<g[i][j]<<' '<<g[pos][now]<<endl;*/
if(used[i][j]&&g[i][j]+1==g[pos][now])
{
tmp=print(j,i);
if(vec.empty())vec=tmp;
else
{
Down(k,vec.size()-1,0)
if(vec[k]!=tmp[k])break;
if(~k&&vec[k]>tmp[k])vec=tmp;
}
}
}
if(!vec.empty())
{
vec.push_back(c[pos]);
/*h[pos][now]=vec;*/
return vec;
}
}
}
int main()
{
int Q,p,i,j;
vector<int>vec;
cin>>Q>>p;
For(i,1,p)cin>>c[i];
sort(c+1,c+p+1,greater<int>());
f[0][0]=1;
For(i,1,p)
For(j,0,Q)
if(j<c[i])
{
f[i][j]=f[i-1][j];
g[i][j]=g[i-1][j];
used[i][j]=0;
}
else
{
if(!f[i-1][j]&&!f[i][j-c[i]])continue;
if(!f[i-1][j]||f[i-1][j]&&f[i][j-c[i]]&&g[i][j-c[i]]+1-used[i][j-c[i]]<=g[i-1][j])f[i][j]=used[i][j]=1,g[i][j]=g[i][j-c[i]]+1-used[i][j-c[i]];
else
{
f[i][j]=1;
used[i][j]=0;
g[i][j]=g[i-1][j];
}
}
cout<<g[p][Q]<<' ';
Down(i,p,1)
if(used[i][Q])break;
vec=print(Q,i);
Down(i,vec.size()-1,0)cout<<vec[i]<<' ';
return 0;
}
//#include<bits/stdc++.h>
//using namespace std;
//#define N 105
//#define NN 20005
//#define For(i,x,y)for(i=x;i<=(y);i++)
//int c[N];
//bool f[N][NN];
//vector<int>vec[N][NN];
//bool pd(vector<int>&x,vector<int>&y)
//{
// return x.size()<y.size()||x.size()==y.size()&&x<y;
//}
//int main()
//{
// bool bo;
// int Q,p,i,j,k;
// cin>>Q>>p;
// For(i,1,p)cin>>c[i];
// sort(c+1,c+p+1);
// f[0][0]=1;
// For(i,1,p)
// For(j,0,Q)
// {
// f[i][j]=f[i-1][j];
// vec[i][j]=vec[i-1][j];
// For(k,1,j/c[i])
// if(f[i-1][j-c[i]*k])
// {
// vec[i-1][j-c[i]*k].push_back(c[i]);
// if(!f[i][j]||pd(vec[i-1][j-c[i]*k],vec[i][j]))f[i][j]=1,vec[i][j]=vec[i-1][j-c[i]*k];
// vec[i-1][j-c[i]*k].pop_back();
// }
// /*if(j>=c[i]&&f[i-1][j-c[i]])
// {
// vec[i-1][j-c[i]].push_back(c[i]);
// if(!f[i][j]||pd(vec[i-1][j-c[i]],vec[i][j]))f[i][j]=1,vec[i][j]=vec[i-1][j-c[i]];
// vec[i-1][j-c[i]].pop_back();
// }
// if(j>=c[i]&&f[i][j-c[i]])
// {
// bo=0;
// if(vec[i][j-c[i]].empty()||vec[i][j-c[i]].back()<c[i])bo=1,vec[i][j-c[i]].push_back(c[i]);
// if(!f[i][j]||pd(vec[i][j-c[i]],vec[i][j]))f[i][j]=1,vec[i][j]=vec[i][j-c[i]];
// if(bo)vec[i][j-c[i]].pop_back();
// }
// if(i==1&&j==3)cerr<<vec[i][j].size()<<endl;*/
// }
// /*p=3;
// Q=7247+949*1;
// cerr<<f[p][Q]<<' ';*/
// cout<<vec[p][Q].size();
// For(i,0,int(vec[p][Q].size())-1)cout<<' '<<vec[p][Q][i];
// return 0;
//}
/*
16737
4
904
909
916
949
*/