高中生做网站网页,如何做网页设计,广州建站哪个济南兴田德润实惠吗,wordpress电台模板目录 1 基础知识2 模板3 工程化 1 基础知识
暂无。。。
2 模板
暂无。。。
3 工程化
题目1#xff1a;小国王。
解题思路#xff1a;状态压缩DP。
状态定义f[i][j][a]#xff1a;表示已经考虑了前i行#xff0c;并且摆放了j个国王#xff0c;且第i行的状态是a的总方… 目录 1 基础知识2 模板3 工程化 1 基础知识
暂无。。。
2 模板
暂无。。。
3 工程化
题目1小国王。
解题思路状态压缩DP。
状态定义f[i][j][a]表示已经考虑了前i行并且摆放了j个国王且第i行的状态是a的总方案数。
定义第i行的合理状态a二进制表示中没有连续的两个1。与第i-1行不冲突比如第i-1行的状态是b那么需要满足a b 0和a | b没有连续的两个1。
状态转移先计算出所有合法的状态存储在向量states中然后预先处理出每个状态a可以从状态b转移过来unordered_mapint, vectorint g。
C代码如下
#include iostream
#include vector
#include unordered_mapusing namespace std;const int N 12, M 1 N;
int n, m;
long long f[N][N*N][M];
vectorint states; //合法的状态
unordered_mapint,vectorint g;bool check(int x) {//是否存在连续的两个1for (int i 0; i 31; i) {if ((x i 1) (x (i 1) 1)) {return false; //非法的状态} }return true;
}int get_cnt(int x) {//二进制中1的个数int res 0;for (int i 0; i 31; i) {if (x i 1) res 1;}return res;
}int main() {cin n m;for (int i 0; i 1 n; i) {if (check(i)) {states.emplace_back(i);}}for (auto a : states) {for (auto b : states) {if ((a b) 0 check(a | b)) {g[a].emplace_back(b);}}}//初始化状态f[0][0][0] 1;for (int i 1; i n 1; i) {for (int j 0; j m; j) {for (auto a : states) {for (auto b : g[a]) {int cnt get_cnt(a);if (j cnt) {f[i][j][a] f[i-1][j-cnt][b];}}}}}cout f[n1][m][0] endl;return 0;
}题目2玉米田。
状态定义f[i][a]考虑前i行且第i行的状态是a的所有方案数。
第i行的状态a需要满足二进制表示中没有两个相邻的1。与第i-1行的状态b不冲突即(a b) 0。只能在肥沃的土地种玉米。
可以预处理出合法的状态存储在向量states中然后考虑每一行的肥沃土地可以换一种思路将贫瘠的土地构成的状态记为row[i]则需要满足(a row[i]) 0。
C代码如下
#include iostream
#include vector
#include unordered_mapusing namespace std;const int N 15, M 1 N, mod 1e8;
int n, m;
vectorint row; //表示不育
vectorint states;
unordered_mapint, vectorint g; //状态a可以由状态b转移过来
int f[N][M];bool check(int x) {for (int i 0; i 31; i) {if ((x i 1) (x (i 1) 1)) {return false; //非法状态}}return true; //合法状态
}int main() {cin n m; //n行m列row.emplace_back(0);for (int i 0; i n; i) {int t 0;for (int j 0; j m; j) {int x;cin x;if (x 0) {t 1 j;}}row.emplace_back(t);//不育}for (int i 0; i 1 m; i) {if (check(i)) {states.emplace_back(i);}}for (auto a : states) {for (auto b : states) {if ((a b) 0) {g[a].emplace_back(b);}} }//状态计算f[0][0] 1;for (int i 1; i n 1; i) {for (auto a : states) {if (a row[i]) continue;for (auto b : g[a]) {if (b row[i-1]) continue;if ((a b) 0) {f[i][a] (f[i][a] (f[i-1][b] % mod)) % mod;}}}}cout f[n1][0] endl;return 0;
}题目3炮兵阵地。
解题思路状态压缩DP。由于空间有限所以需要用到滚动数组在原地址上更新滚动数组暂时没有理解到本质先空着。
状态定义f[i][a][b]考虑前i行且第i-1行的状态是a第i行的状态是b该case下的最大摆放炮兵的数目。
合法状态两个1之间至少空了2个位置。第i行、第i-1行和第i-2行任意两个不能互相攻击到记第i-1行的状态为a第i行的状态为b第i-2行的状态为c那么有((a b) | (a c) | (b c)) 0。
同时还有一个额外需要考虑的就是山顶不能放置炮兵记第i行山顶的状态为row[i]那么需要满足(b row[i]) 0。
C代码如下
#include iostream
#include vector
#include cstring
#include unordered_mapusing namespace std;const int N 110, M 1 12;int n, m;
vectorint states;
vectorint row(N, 0);
int f[2][M][M];bool check(int x) {for (int i 0; i 31; i) {if ((x i 1) ((x (i 1) 1) || (x (i 2) 1))) {return false; //非法状态}}return true;
}int get_count(int x) {int res 0;for (int i 0; i 31; i) {if (x i 1) res 1;}return res;
}int main() {cin n m;for (int i 1; i n; i) {int t 0;for (int j 0; j m; j) {char c;cin c;if (c H) {t 1 j;}}row[i] t;}//处理合理状态for (int i 0; i 1 m; i) {if (check(i)) {states.emplace_back(i);}}//计算状态for (int i 1; i n; i) {for (auto a : states) {//第i-1行的状态是afor (auto b : states) { //第i行的状态是bfor (auto c : states) {//第i-2行的状态是cif ((a row[i-1]) || (b row[i])) continue; //山上不能放置炮兵if ((a b) || (a c) || (b c)) continue; //行与行之间不能攻击到f[i 1][a][b] max(f[i 1][a][b], f[i - 1 1][c][a] get_count(b));}}}}int res 0;for (auto a : states) {for (auto b : states) {res max(res, f[n 1][a][b]);}}cout res endl;return 0;
}题目4愤怒的小鸟。
解题思路没有看懂有时间再推敲。
C代码如下
#include cstring
#include iostream
#include algorithm
#include cmath#define x first
#define y secondusing namespace std;typedef pairdouble, double PDD;const int N 18, M 1 N;
const double eps 1e-8;int n, m;
PDD q[N];
int path[N][N];
int f[M];int cmp(double x, double y) {if (fabs(x - y) eps) return 0;if (x y) return -1;return 1;
}int main() {int T;cin T;while (T--) {cin n m;for (int i 0; i n; i) cin q[i].x q[i].y;memset(path, 0, sizeof path);for (int i 0; i n; i) {path[i][i] 1 i;for (int j 0; j n; j) {double x1 q[i].x, y1 q[i].y;double x2 q[j].x, y2 q[j].y;if (!cmp(x1, x2)) continue;double a (y1 / x1 - y2 / x2) / (x1 - x2);double b y1 / x1 - a * x1;if (cmp(a, 0) 0) continue;int state 0;for (int k 0; k n; k) {double x q[k].x, y q[k].y;if (!cmp(a * x * x b * x, y)) state 1 k;}path[i][j] state;}}memset(f, 0x3f, sizeof f);f[0] 0;for (int i 0; i 1 1 n; i) {int x 0;for (int j 0; j n; j) {if (!(i j 1)) {x j;break;}}for (int j 0; j n; j) {f[i | path[x][j]] min(f[i | path[x][j]], f[i] 1);}}cout f[(1 n) - 1] endl;}return 0;
}
