本文主要是介绍spot 状压dp，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目大意:数轴上有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;
}这篇关于spot 状压dp的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
