柳州做网站的企业,网站建设方向市场分析,美食网站建设项目预算,一个人可以做几个网站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
