[洛谷 2396]yyy loves Maths VII

题目链接

https://www.luogu.org/problemnew/show/P2396

题解

数据范围并不大,我们考虑用状压DP的方法解决本题。

定义状态\(f[i]\)代表使用集合\(i\)中的卡片完成游戏的方案数,\(dist[i]\)表示使用集合\(i\)中的卡片走到的位置。

我们在进行状态转移的时候,枚举这一次要用的卡片\(j\),则\(f[i]= \sum_{j \in i} f[j]\)。

别忘了跳过厄运数字。(\(dist\)就是来做这个判断的)

然而本题数据范围卡的很紧,懒得加太多常数优化怎么办,那就吸氧吧233

#include <cstdio>
#include <algorithm>
#define MOD 1000000007
using namespace std;
int f[17000005],dist[17000005];
int b1,b2;
inline int lowbit(int x)
{
 return x&(-x);
}
int main()
{
 int n,m;
 scanf("%d",&n);
 for(int i=0;i<n;i++)
  scanf("%d",&dist[1<<i]);
 scanf("%d",&m);
 if(m==1)scanf("%d",&b1);
 else if(m==2)scanf("%d%d",&b1,&b2);
 f[0]=1;
 int maxx=(1<<n)-1;
 for(int i=1;i<=maxx;i++)
 {
  int x=i,y=lowbit(x);
  dist[i]=dist[i^y]+dist[y];
  if(dist[i]==b1||dist[i]==b2)continue;
  while(y)
  {
   f[i]+=f[i^y];
   if(f[i]>=MOD)f[i]-=MOD;
   x^=y;
   y=lowbit(x);
  }
 }
 printf("%d\n",f[maxx]);
 return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注