从1到100这100个数内选尽量多的数字，使得任意两个数的差既不是4也不是7.

思路是设 $f_{i,S}$ 表示在前 $i$ 个数内最多能选多少个数满足题意。$S$ 是个类似状压的状态表示末 $7$ 个数的选取情况。

枚举下一个数是否选取，就有了这样的代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=1e5+7;
const int V=20;
LL f[maxn][V],p[maxn][V];
LL N,ans,ansS;
bool include(int S,int inx){return S&(1<<(inx-1));}
int main(){
	N=100;
	memset(f,-0x3f,sizeof(f));
	f[1][0]=0;
	f[1][1]=1;
	for(int i=1;i<N;i++){
		for(int S=0;S<(1<<7);S++){
			int NXT=((S<<1)&(255));
			//f[i+1][NXT]=max(f[i+1][NXT],f[i][S]);
			if(f[i][S]>f[i+1][NXT])
				f[i+1][NXT]=f[i][S],p[i][NXT]=S;
			if(include(S,4)||include(S,7))continue;
			//f[i+1][NXT|1]=max(f[i+1][NXT|1],f[i][S]+1);
			if(f[i][S]+1>f[i+1][NXT|1])
				f[i+1][NXT|1]=f[i][S]+1,p[i][NXT|1]=S;
		}
	}
	for(int S=0;S<(1<<7);S++)
		if(f[N][S]>ans)ans=f[N][S],ansS=S;
	cout<<ans<<endl;
	for(int i=N;i>=1;i--){
		if(ansS&1)cout<<i<<' ';
		ansS=p[i][ansS];
	}
	return 0;
}

结果输出方案是：

53
100 99 98 96 94 93 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 3 1

可以看到1和8同时出现在了里面。

是最开始状态的定义出了问题吗？还是转移出了问题？还是需要用其他的办法？顺便问下传统whk法正解是什么