网站建设与管理的总结报告,廊坊关键词seo排名方案,推广网站的步骤,山东网站建设代理problem 在NN的棋盘里面放K个国王每个国王会攻击它周围的一圈共8个格子使他们互不攻击#xff0c;共有多少种摆放方案N 9solution 用01串表示某一行放置的情况 首先枚举当前做到第几行#xff0c;以及当前一共放了几颗棋子。于是状态f[i][j][k]表示到第i行#xff0c;一… problem 在N×N的棋盘里面放K个国王每个国王会攻击它周围的一圈共8个格子使他们互不攻击共有多少种摆放方案N 9solution 用01串表示某一行放置的情况 首先枚举当前做到第几行以及当前一共放了几颗棋子。于是状态f[i][j][k]表示到第i行一共放j个棋子包括这之前的且第i行的状态是k的方案数。再考虑转移。这一行肯定是由上一行的状态转移过来的那么我们可以再枚举上一行的状态。很自然的发现这会超时。每次枚举一种状态就需要2^9两重循环已经快爆掉了我们可以发现一件事情。比如n5,我们每次枚举到的11111,11011,10111,01011这些状态都是无效的。那么我们可以先预处理一下对于每一行的所有可行的状态就是不能有连续的1。这样的效率仍然不高——我们还可以对于每种可行的状态i,j预处理i和j是否能够相邻这样我们在DP的时候就可以O(1)来转移了。这里也可以不预处理每次直接判断ij能否相邻也可。最后记得开long long。 codes #includeiostream
using namespace std;
const int maxn 512;
typedef long long LL;
int c1[maxn], cnt[maxn], c2[maxn][maxn];
LL ans, f[10][100][maxn];
int main(){int n, m;cinnm;int all (1n)-1;for(int i 0; i all; i){if((i(i1))0){c1[i] 1;for(int x i; x; x 1) cnt[i] (x1);}}for(int i 0; i all; i)if(c1[i])f[1][cnt[i]][i] 1;for(int i 1; i n; i){for(int j 0; j all; j)if(c1[j]){for(int k 0; k all; k)if(c1[k]){if(((jk)0)((j(k1))0)((j(k1))0)){for(int p cnt[j]; pcnt[k]m; p)f[i1][pcnt[k]][k] f[i][p][j];}}}}for(int i 0; i all; i)ans f[n][m][i];coutans\n;return 0;
} 转载于:https://www.cnblogs.com/gwj1314/p/9444821.html
