我仍不理解
初始化dp[1][0][0]和初始化dp[0][0][0]的差别在哪 我与”苟且的狮子“的代码几乎一模一样,但是我必须用前者方式来初始化,而他要用后者方式来初始化。。。
#include<iostream>
using namespace std;
using ll = long long;
ll dp[10][999][99];//第三维表示到目前为止,共使用了多少国王
bool state[999];
int king[999];
int main()
{
int n, kk;
cin >> n >> kk;
for (int i = 0; i < (1 << n); ++i)
{
state[i] = (!(i & (i << 1)) && !(i & (i >> 1)));//首先本身是否为“可塑之才”(相邻就直接pass掉)
int t = i;
while (t)
{
king[i] += (t & 1);//预处理,每一状态对应的国王数
t = (t >> 1);
}
if (king[i] > kk)
state[i] = 0;
// cout<<state[i]<<endl;正确
}
dp[0][0][0] = 1; //这样初始化也是对的,但是我不能理解为什么"苟且的狮子"dp[1][0][0]初始化也是对的,而我就会错
/* for(int i=0;i<(1<<n);++i)
{
if(king[i]<=kk)
dp[1][i][king[i]]=1;
}
*/
for (int i = 1; i <= n; ++i)//枚举每一行
{
//cout<<"第"<<i<<"行"<<endl;
for (int j = 0; j < (1 << n); ++j)//枚举当前行的状态
{
if (!state[j])//不可塑,跳过
continue;
//先将当前行以前的国王数确定下来,这样就不用担心超出数量上限了
for (int m = king[j]; m <= kk; ++m)
{
for (int k = 0; k < (1 << n); ++k)//枚举上一行的状态
{
if (!state[k])
continue;
if ((j << 1) & k)
continue;
if ((j >> 1) & k)
continue;
if (j & k)
continue;
dp[i][j][m] += dp[i - 1][k][m - king[j]];//好像有漏洞,
// cout<<i<<"*"<<j<<"*"<<m<<":"<<dp[i][j][m]<<endl;
//还应该注意国王数量上限
//不用担心等号左侧总会有很多国王
//因为我把从零到一的每个状态都遍历了一遍啊,比如状态1,不就只有一个国王吗。
}
}
}
}
ll sum = 0;
// for (int j = 1; j <= n; ++j)
for (int i = 0; i < (1 << n); ++i)
{
sum += dp[n][i][kk];
}
cout << sum;
}