2017多校5 1008 Rikka with Subset

本文主要是介绍2017多校5 1008 Rikka with Subset，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

http://acm.hdu.edu.cn/showproblem.php?pid=6092

这道题因为比赛的时候卡在了1006上，所以没看。清题的时候一看，感觉是能做的，求一串数列，总和为m，并且会给出这个数列中所有子序列和等于1到m所有的情况数。

可以想到，一个较大的数可以是由几个小数相加得到，也可以从一个等于该数的数得到，并且这几个小数也适用这个规则，那么就可以从小到大用01背包动态规划思想去处理，出现了哪些数以及该数出现的次数。

#include<iostream>
#include<cstring>
using namespace std;
#define ma(a) memset((a),0,sizeof((a)))
int dp[11111],num[11111],a[11111],ans[11111];
int main(){long long t;cin>>t;long long n,m;while(t--){ma(dp);ma(a);ma(ans);int i,j,k;scanf("%lld%lld",&n,&m);for(i=0;i<=m;i++)scanf("%d",&a[i]);dp[0]=1;int _js=0;for(i=1;i<=m;i++){num[i]=a[i]-dp[i];for(j=0;j<num[i];j++){ans[_js++]=i;for(k=m;k>=i;k--)dp[k]+=dp[k-i];}}int q=0;for(i=0;i<_js;i++){if(q++)printf(" ");printf("%d",ans[i]);}cout<<endl;}return 0;
}

这篇关于2017多校5 1008 Rikka with Subset的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---