首页 > 代码库 > hdu 6092

hdu 6092

思路:根据前面可能造成后面的情况,再相减即为该数的个数,背包

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N=1e4+10;
 4 
 5 int a[N],b[N],dp[N];
 6 
 7 
 8 int main(){
 9     int t ;
10     cin>>t;
11     while(t--){
12         int n,m;
13         memset(dp,0,sizeof(dp));
14         scanf("%d%d",&n,&m);
15         for(int i=0;i<=m;i++) scanf("%d",&b[i]);
16         int l=0;
17         memset(dp,0,sizeof(dp));
18         dp[0]=1;
19         for(int i=1;i<m;i++){
20             int x=b[i]-dp[i];
21             for(int j=1;j<=x;j++){
22                 a[++l]=i;
23                 for(int k=m;k>=i;k--)
24                     dp[k]+=dp[k-i];
25             }
26         }
27         for(int i=1;i<=l;i++){
28             printf("%d",a[i]);
29             if(i!=l) printf(" ");
30             else printf("\n");
31         }
32     }
33     return 0;
34 }

 

hdu 6092