题目链接
大概意思就是Q的体力，n个烧烤店，m个特殊的，要去至少k个。
告诉了我们各个点的到达方案数的情况下，求解恰好Q体力且经过至少K个特殊烧烤店的方案数。
问题分析： n很小，但有50，直接状态压缩不可取。 m k只有10
我们先要想想怎么设计状态，状态由什么转移。
特殊烧烤店显然要靠状态压缩，然后我们还需要体力的状态，emm还缺点什么是吧。我们再定义一维表示以 X 为终点的状态。好像差不多了。
定义dp[【0~ 1<<m】][t][j] 为状态下，恰好花费了t点体力且到达j 的方案数
我们的体力必须完全更新了才能进入下一步，即体力在最外层枚举。然后是枚举状态，枚举上一步的到达点，枚举下一步的到达点。
具体请见代码细节；
#include<bits/stdc++.h>#include<stdlib.h>#include<algorithm>#include<stdio.h>#include<string.h>#include<queue>#include<time.h>#include <cstdio>#include <iostream>#include <vector>#define ll long long#define int long long#define inf 0x3f3f3f3f#define mods 0802#define modd 998244353#define PI acos(-1)#define fi first#define se second#define lowbit(x) (x&(-x))#define mp make_pair#define pb push_back#define si size()#define E exp(1.0)#define fixed cout.setf(ios::fixed)#define fixeds(x) setprecision(x)#define IOS ios::sync_with_stdio(false);cin.tie(0)using namespace std;ll gcd(ll a,ll b){if(a<0)a=-a;if(b<0)b=-b;return b==0?a:gcd(b,a%b);}template<typename T>void read(T &res){bool flag=false;char ch;while(!isdigit(ch=getchar()))(ch=='-')&&(flag=true);for(res=ch-48;isdigit(ch=getchar());res=(res<<1)+(res<<3)+ch - 48);flag&&(res=-res);}ll lcm(ll a,ll b){return a*b/gcd(a,b);}ll qp(ll a,ll b,ll mod){ll ans=1;if(b==0){return ans%mod;}while(b){if(b%2==1){b--;ans=ans*a%mod;}a=a*a%mod;b=b/2;}return ans%mod;}//快速幂%ll qpn(ll a,ll b, ll p){ll ans = 1;a%=p;while(b){if(b&1){ans = (ans*a)%p;--b;}a =(a*a)%p;b >>= 1;}return ans%p;}//逆元 (分子*qp(分母,mod-2,mod))%mod;ll cnt[60];ll G[60][60];ll dp[(1<<12)][51][51];//ll num=0;ll kk;ll m;ll check(ll x){ll nu=0;for(int i=0; i<m; i++){if(((1<<i)&x))nu++;}return nu>=kk;}signed main(){ll n,Q;read(n);read(m);read(kk);read(Q);for(int i=1; i<=m; i++){ll x;read(x);x--;cnt[x]=i;//特殊}for(int i=0; i<n; i++){for(int j=0; j<n; j++){read(G[i][j]);}}dp[0][0][0]=1;//状态/Q/终点for(int t=0; t<Q; t++){// 体力for(int j=0; j<(1<<m); j++){//状态for(int k=0; k<n; k++){// 上轮到达if(cnt[k]&&!(j&(1<<(cnt[k]-1))))continue;if(!dp[j][t][k])continue;for(int p=0; p<n; p++){if(!G[k][p])continue;if(cnt[p]){ll ok=j|(1<<(cnt[p]-1));dp[ok][t+1][p]+=(dp[j][t][k]%mods*G[k][p]%mods)%mods;}else{dp[j][t+1][p]+=(dp[j][t][k]%mods*G[k][p]%mods)%mods;}}}}}ll ans=0;for(int i=0; i<(1<<m); i++){if(check(i)){for(int j=0; j<n; j++){ans=(ans+dp[i][Q][j])%mods;}}}printf("%lld",ans);}
如果觉得《CSUSTOJ 我爱吃烧烤 (状压dp)》对你有帮助，请点赞、收藏，并留下你的观点哦！
