教我***儿子做题.
https://www.acwing.com/problem/content/173/ 这个题的思路和这个题目是类似的.
我们可以先进行排序,预处理k/2的种类存入一个数组..然后另外一半再进行dfs.这种做法很优但是对于这个题目来说.因为数据水,就不至于,但是还是写下.
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=105; const int M=1e6+5; int k,m; int a[10]; int v[10][N]; ll ans=0; ll w[M]; ll tot=0; void dfs1(int u,int val) { if(u>k/2) { w[tot++]=val; return; } for(int i=1;i<=a[u];i++) { dfs1(u+1,val+v[u][i]); } dfs1(u+1,val); }//预处理k/2的 void dfs2(int u,int val) { if(u>k) { ans+=tot-(upper_bound(w,w+tot,m-val)-w); return; } for(int i=1;i<=a[u];i++) { dfs2(u+1,val+v[u][i]); } dfs2(u+1,val); } int main() { while(cin>>k>>m) { ans=0;tot=0; for(int i=1;i<=k;i++) { cin>>a[i]; for(int j=1;j<=a[i];j++) { scanf("%d",&v[i][j]); } sort(v[i]+1,v[i]+1+a[i]); } dfs1(1,0);//层数 价值 sort(w,w+tot); dfs2(k/2+1,0); cout<<ans<<endl; } return 0; }
另外一个方法就是直接dfs,但是这样绝对是可以卡的.代码如下:
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=105; int k,m; int a[10]; int v[10][N]; ll ans=0; void dfs(int u,int val) { if(u>k+1) return; if(val>m) { ll temp=1; for(int i=u;i<=k;i++) { temp*=(a[i]+1); } ans+=temp; return; } for(int i=1;i<=a[u];i++) { dfs(u+1,val+v[u][i]); } dfs(u+1,val); } int main() { while(cin>>k>>m) { ans=0; for(int i=1;i<=k;i++) { cin>>a[i]; for(int j=1;j<=a[i];j++) { scanf("%d",&v[i][j]); } sort(v[i]+1,v[i]+1+a[i]); } dfs(1,0);//层数 价值 cout<<ans<<endl; } return 0; }