题目大意:数轴上有n个泥点，共有m个木板，求最少用几个木板可以覆盖全部泥点，并求最优方案数(n,m<=15)
看范围，肯定是状压
f[i][j]表示前i个泥点都被覆盖，使用的木板集合为j
转移:f[ii][j|bit[k]]+=f[i][j]*(r-l+1)
ii表示枚举木板k能转移到的所有位置,r,l分别表示可行的左右端点
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #define mod 1000000007ll using namespace std; int n,m,bit[20],num=50; long long pos[20],l[20],d[20][20],len,f[18][1<<16+5],ans=0,L,R; bool bo=0; int getn(int x){ int tot=0,a=0; while(x){ a=x%2; if(a==1) tot++; x/=2; } return tot; } int main() { //freopen("spot.in","r",stdin); //freopen("spot.out","w",stdout); bit[0]=1; for(int i=1;i<=16;i++) bit[i]=bit[i-1]<<1; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%lld",&pos[i]); sort(pos+1,pos+n+1); pos[n+1]=0x7fffffffffll; for(int i=1;i<=n;i++) for(int j=i;j<=n;j++) d[i][j]=pos[j]-pos[i]; scanf("%d",&m); for(int i=1;i<=m;i++) scanf("%lld",&l[i]); sort(l+1,l+m+1); f[0][0]=1; for(int i=0;i<=n;i++){ for(int j=0;j<bit[m];j++){ if(!f[i][j]) continue; for(int k=1;k<=m;k++){ if((j|bit[k-1])==j) continue; for(int ii=i+1;ii<=n;ii++){ if(d[i+1][ii]<l[k]){ L=pos[ii]-l[k]+1; R=min(pos[i+1],pos[ii+1]-l[k]); f[ii][j|bit[k-1]]+=f[i][j]*(R-L+1); f[ii][j|bit[k-1]]%=mod; } } } } } for(int j=0;j<bit[m];j++) if(f[n][j]) num=min(num,getn(j)); for(int j=0;j<bit[m];j++){ if(f[n][j]&&getn(j)==num){ bo=1; ans+=f[n][j]; ans%=mod; } } if(!bo){ printf("NO\n"); return 0; } else printf("%d\n%lld\n",num,ans); return 0; }