51Nod 1386 - 双马尾机器人

题目精选 平衡规划 状压dp

题意

      给定 $n$ 和 $k$ ，我们要在 $1,2,3,...,n$ 中选择若干的数，每一种选择的方案被称为选数方案。
      我们定义一种选数方案是合法的，当且仅当 $k$ 没有被选，且任意两个选的数互质。
      我们定义一种选数方案是极大的，当且仅当它是合法的，且不能再从剩下的数中选择任意一个，或者选的是 $k$ 。
      求极大的选数方案的最小的选的个数。

$1\leq T\leq 50$
$1\leq n\leq 1000，1\leq k\leq n且k不是质数$

分析

      考虑一下怎样的选数方案是极大的。也就是我们要选1，以及 $1...n$ 中的每个质数都要在我们选择的数中出现。我们要考虑满足上述要求的情况下选最少的数。
      对于 $\leq \sqrt n$ 的质数，只有17个，我们考虑通过状态压缩进行记录。对于 $>\sqrt n$ 的质数，每个数最多只有一个，我们根据这个质数对所有的数进行分类。然后考虑状压dp。
      设 $f[i][j]$ 表示当前弄到了第$i$个大质数，小质数的填充情况为 $j$ 的方案数。
      总之它是一种平衡规划，对于比较小的质数直接状压，对于比较大的就记录下来，按照它来分类转移。

      注意要把大质数个数和n给均摊下来。每个数按照对应的大质数分类。把 $O(大质数*n)$ 变成 $O(大质数+n)$ 。

实现

#include <bits/stdc++.h>
using namespace std;
#define F(i,a,b) for (int i=(a);i<=(b);i++)
#define D(i,a,b) for (int i=(a);i>=(b);i--)
#define fore(v,u) for (vector<int>::iterator v=g[u].begin();v!=g[u].end();v++)
#define LL long long
#define LD long double
LL rd(void) {
    LL x=0,f=1; char c=getchar();
    for (;!isdigit(c);c=getchar()) if (c=='-') f=-1;
    for (;isdigit(c);c=getchar()) x=x*10+c-'0';
    return x*f;
}
char rdc(void) {
    char c=getchar();
    while (!isalpha(c))
        c=getchar();
    return c;
}
const int M_N=1024;
const int N=1000;
int pri[M_N],vis[M_N],tot;
int num[M_N];
int big_cnt,kd[M_N],type[M_N][M_N];
const int M_ALL=2048;
const int M_BIG=170;
const int small_cnt=11;
const int all=(1<<small_cnt)-1;
const int INF=0x7fffffff>>1;
int f[M_BIG][M_ALL];
int main(void) {
    #ifndef ONLINE_JUDGE
        freopen("sdchr.in","r",stdin);
        freopen("sdchr.out","w",stdout);
    #endif
    vis[1]=1;
    F(i,2,N) {
        if (!vis[i]) pri[++tot]=i;
        F(j,1,tot) {
            if (i*pri[j]>N) break;
            vis[i*pri[j]]=1;
            if (i%pri[j]==0) break;
        }
    }
    F(i,1,N) {
        int c=0;
        F(j,1,small_cnt)
            if (i%pri[j]==0)
                c|=(1<<(j-1));
        num[i]=c;
    }
    F(i,1,N) F(j,small_cnt+1,tot) if (i%pri[j]==0) kd[i]=j-small_cnt;
    F(i,1,N) type[kd[i]][++type[kd[i]][0]]=i;
    int nT=rd();
    F(c,1,nT) {
        int n=rd(),k=rd();
        big_cnt=small_cnt; while (big_cnt+1<=tot&&pri[big_cnt+1]<=n) big_cnt++; big_cnt-=small_cnt;
        F(t,0,big_cnt) F(i,0,all) f[t][i]=INF;
        f[0][0]=0;
        F(i,0,all) if (f[0][i]!=INF)
            F(now,1,type[0][0]) {
                int j=type[0][now];
                if (j<=n&&j!=k&&!(i&num[j]))
                    f[0][i|num[j]]=min(f[0][i|num[j]],f[0][i]+1);
            }
        if (pri[small_cnt+1]>n) {
            int star=small_cnt;
            if (pri[star]>n) {
                while (star-1>0&&pri[star-1]>n)
                    star--;
                star--;
            }
            printf("Case #%d: %d\n",c,f[0][(1<<star)-1]+(k!=1));
            continue;
        }
        F(t,1,big_cnt)
            F(i,0,all) if (f[t-1][i]!=INF)
                F(now,1,type[t][0]) {
                    int j=type[t][now];
                    if (j<=n&&j!=k&&!(i&num[j]))
                        f[t][i|num[j]]=min(f[t][i|num[j]],f[t-1][i]+1);
                }
        printf("Case #%d: %d\n",c,f[big_cnt][all]+(k!=1));
    }
    return 0;
}