明薇通网站建设首选,别人带做的网站关闭了权限咋办,东莞外贸网站建设策划方案,可以建设彩票网站吗棋盘式的f[i][j]中表示状态的j可以是状态本身也可以是在合法状态state中的下标
用状态本身比较方便#xff0c;用下标比较省空间
用下标的话可以开id[M]数组记录一下 蒙德里安的梦想
求把 NM的棋盘分割成若干个 12的长方形#xff0c;有多少种方案。
例如当 N2#xff0…棋盘式的f[i][j]中表示状态的j可以是状态本身也可以是在合法状态state中的下标
用状态本身比较方便用下标比较省空间
用下标的话可以开id[M]数组记录一下 蒙德里安的梦想
求把 N×M的棋盘分割成若干个 1×2的长方形有多少种方案。
例如当 N2M4时共有 5 种方案。当 N2M3时共有 3 种方案。
如下图所示 输入格式
输入包含多组测试用例。
每组测试用例占一行包含两个整数 N和 M。
当输入用例 N0M0时表示输入终止且该用例无需处理。
输出格式
每个测试用例输出一个结果每个结果占一行。
数据范围
1≤N,M≤11
输入样例
1 2
1 3
1 4
2 2
2 3
2 4
2 11
4 11
0 0输出样例
1
0
1
2
3
5
144
51205
先放横着的空位竖着的就只有一种摆法
f[i][j]表示前i-1列已摆好j表示第i列中有哪些行是凸出来的
核心思路是看第i-1行是否合法
#includebits/stdc.h
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl \nusing namespace std;typedef pairint, int PII;
typedef long long ll;const int N 12, M 1 11;int n, m;
ll f[N][M];//前i-1列已摆好第i列中有哪些行是凸出来的
vectorint state[M];
bool st[M];int main()
{IOSwhile(cin n m, n){for(int i 0; i 1 n; i )//处理合法状态 {st[i] true;int cnt 0;for(int j 0; j n; j ){if(i j 1){if(cnt % 2){st[i] false;break;}cnt 0;}else cnt ;}if(cnt % 2)st[i] false;}for(int i 0; i 1 n; i ) {state[i].clear();for(int j 0; j 1 n; j ){if((i j) 0 st[i | j]){state[i].push_back(j);}}}memset(f, 0, sizeof f);f[0][0] 1;for(int i 1; i m; i ){for(int j 0; j 1 n; j )//i-1 i{for(auto k : state[j])//i-2 i-1{//核心是看i-1列是否合法 f[i][j] f[i - 1][k];}}}cout f[m][0] endl;}return 0;
}
最短Hamilton路径
给定一张 n 个点的带权无向图点从 0∼n−1 标号求起点 0 到终点 n−1 的最短 Hamilton 路径。
Hamilton 路径的定义是从 00 到 n−1 不重不漏地经过每个点恰好一次。
输入格式
第一行输入整数 n。
接下来 n行每行 n 个整数其中第 i 行第 j 个整数表示点 i 到 j 的距离记为 a[i,j]。
对于任意的 x,y,z数据保证 a[x,x]0a[x,y]a[y,x]并且 a[x,y]a[y,z]≥a[x,z]。
输出格式
输出一个整数表示最短 Hamilton 路径的长度。
数据范围
1≤n≤20 0≤a[i,j]≤1e7
输入样例
5
0 2 4 5 1
2 0 6 5 3
4 6 0 8 3
5 5 8 0 5
1 3 3 5 0输出样例
18 f[state][j]state表示哪些点走过j表示当前停留在哪个点
#includebits/stdc.h
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl \nusing namespace std;typedef pairint, int PII;
typedef long long ll;const int N 20, M 1 N;int n;
int f[M][N], w[N][N];int main()
{IOScin n;for(int i 0; i n; i )for(int j 0; j n; j )cin w[i][j];memset(f, 0x3f, sizeof f);f[1][0] 0;for(int i 0; i 1 n; i ){for(int j 0; j n; j )//到第j位 {if(i j 1){int t i - (1 j);//去掉第j位 for(int k 0; k n; k )//从k转移 {if(t k 1){f[i][j] min(f[i][j], f[t][k] w[k][j]);}}}}}cout f[(1 n) - 1][n - 1];return 0;
}
小国王
在 n×n 的棋盘上放 k 个国王国王可攻击相邻的 8 个格子求使它们无法互相攻击的方案总数。
输入格式
共一行包含两个整数 n 和 k。
输出格式
共一行表示方案总数若不能够放置则输出00。
数据范围
1≤n≤10, 0≤k≤n^2
输入样例
3 2输出样例
16 f[i][j][k]表示前i层第i层状态为k摆了j个国王
#includebits/stdc.h
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl \nusing namespace std;typedef pairint, int PII;
typedef long long ll;const int N 12, M 1 10, K 110;int n, k;
ll f[N][K][M];
vectorint state;
vectorint head[M];
bool st[M];
int cnt[M];bool check(int x)
{for(int i 0; i n; i ){if(x i 1 x i 1 1)return false;}return true;
}int count(int x)
{int res 0;while(x){if(x 1)res ;x 1;}return res;
}int main()
{IOScin n k;for(int i 0; i 1 n; i ){if(check(i)){state.push_back(i);st[i] true;cnt[i] count(i);}}for(auto a : state){for(auto b : state){if((a b) 0 st[a | b]){head[a].push_back(b);}}}f[0][0][0] 1;for(int i 1; i n 1; i )//10{for(int j 0; j k; j )//100{for(auto a : state)//1000{for(auto b : head[a])//1000{if(j cnt[a])f[i][j][a] f[i - 1][j - cnt[a]][b];}}}}cout f[n 1][k][0];return 0;
}
玉米田
农夫约翰的土地由 M×N个小方格组成现在他要在土地里种植玉米。
非常遗憾部分土地是不育的无法种植。
而且相邻的土地不能同时种植玉米也就是说种植玉米的所有方格之间都不会有公共边缘。
现在给定土地的大小请你求出共有多少种种植方法。
土地上什么都不种也算一种方法。
输入格式
第 11 行包含两个整数 M 和 N。
第 2..M1 行每行包含 N 个整数 0 或 1用来描述整个土地的状况1 表示该块土地肥沃0 表示该块土地不育。
输出格式
输出总种植方法对 108108 取模后的值。
数据范围
1≤M,N≤12
输入样例
2 3
1 1 1
0 1 0输出样例
9 和上一题几乎一模一样
没了个数的限制更简单一点
只是多了一个肥沃土地的限制dp过程中判断即可
#includebits/stdc.h
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl \nusing namespace std;typedef pairint, int PII;
typedef long long ll;const int N 14, M 1 12, mod 100000000;int n, m;
int f[N][M];
vectorint state, head[M];
bool st[M];
int g[N];bool check(int x)
{for(int i 0; i m; i ){if(x i 1 x i 1 1){return false;}}return true;
}int main()
{IOScin n m;for(int i 1; i n; i ){for(int j 0; j m; j ){int x;cin x;g[i] !x j;}}for(int i 0; i 1 m; i ){if(check(i)){state.push_back(i);st[i] true;}}for(auto a : state){for(auto b : state){if((a b) 0){head[a].push_back(b); }}}f[0][0] 1;for(int i 1; i n 1; i ){for(auto A : state){for(auto B : head[A]){ if(g[i] A)continue;if(g[i - 1] B)continue;//这两条语句任意保留一条都能过只保留第一条是保证当前合法才转移当前不合法就没有值//只保留第二条是保证上一行状态合法只从合法状态转移过来不合法虽然有值但不会被转移f[i][A] (f[i][A] f[i - 1][B]) % mod;}}}cout f[n 1][0];return 0;
}
炮兵阵地
司令部的将军们打算在 N×M的网格地图上部署他们的炮兵部队。
一个 N×M的地图由 N行 M列组成地图的每一格可能是山地用 H 表示也可能是平原用 P 表示如下图。
在每一格平原地形上最多可以布置一支炮兵部队山地上不能够部署炮兵部队一支炮兵部队在地图上的攻击范围如图中黑色区域所示 如果在地图中的灰色所标识的平原上部署一支炮兵部队则图中的黑色的网格表示它能够攻击到的区域沿横向左右各两格沿纵向上下各两格。
图上其它白色网格均攻击不到。
从图上可见炮兵的攻击范围不受地形的影响。
现在将军们规划如何部署炮兵部队在防止误伤的前提下保证任何两支炮兵部队之间不能互相攻击即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内在整个地图区域内最多能够摆放多少我军的炮兵部队。
输入格式
第一行包含两个由空格分割开的正整数分别表示 N 和 M
接下来的 N 行每一行含有连续的 M 个字符(P 或者 H)中间没有空格。按顺序表示地图中每一行的数据。
输出格式
仅一行包含一个整数 K表示最多能摆放的炮兵部队的数量。
数据范围
N≤100,M≤10
输入样例
5 4
PHPP
PPHH
PPPP
PHPP
PHHP输出样例
6
f[i][j][j]表示第i行第i-1行状态为j第i行状态为k 状态表示为最大个数。
#includebits/stdc.h
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl \nusing namespace std;typedef pairint, int PII;
typedef long long ll;const int N 110, M 1 10;int n, m;
int g[N];
vectorint state;
int f[2][M][M];
int cnt[M];bool check(int x)
{for(int i 0; i m; i ){if(x i 1 (x i 1 1 || x i 2 1)){return false;}}return true;
}int count(int x)
{int res 0;while(x){if(x 1)res ;x 1;}return res;
}int main()
{IOScin n m;for(int i 1; i n; i ){for(int j 0; j m; j ){char c;cin c;if(c H)g[i] 1 j;}}for(int i 0; i 1 m; i ){if(check(i)){state.push_back(i);cnt[i] count(i);}}for(int i 1; i n 2; i ){for(auto a : state)//i - 2{for(auto b : state)//i - 1{for(auto c : state)//i{if(a b | a c | b c)continue;if(c g[i] | b g[i - 1])continue;//和上题一样判断当前状态合法才转移f[i 1][b][c] max(f[i 1][b][c], f[i - 1 1][a][b] cnt[c]);}}}}cout f[n 2 1][0][0];return 0;
}
愤怒的小鸟
Kiana 最近沉迷于一款神奇的游戏无法自拔。
简单来说这款游戏是在一个平面上进行的。
有一架弹弓位于 (0,0) 处每次 Kiana 可以用它向第一象限发射一只红色的小鸟 小鸟们的飞行轨迹均为形如 yax2bx 的曲线其中 a,b 是 Kiana 指定的参数且必须满足 a0。
当小鸟落回地面即 x 轴时它就会瞬间消失。
在游戏的某个关卡里平面的第一象限中有 n 只绿色的小猪其中第 i 只小猪所在的坐标为 (xi,yi)。
如果某只小鸟的飞行轨迹经过了 (xi, yi)那么第 i 只小猪就会被消灭掉同时小鸟将会沿着原先的轨迹继续飞行
如果一只小鸟的飞行轨迹没有经过 (xi, yi)那么这只小鸟飞行的全过程就不会对第 i 只小猪产生任何影响。
例如若两只小猪分别位于 (1,3) 和 (3,3)Kiana 可以选择发射一只飞行轨迹为 y−x24x 的小鸟这样两只小猪就会被这只小鸟一起消灭。
而这个游戏的目的就是通过发射小鸟消灭所有的小猪。
这款神奇游戏的每个关卡对 Kiana 来说都很难所以 Kiana 还输入了一些神秘的指令使得自己能更轻松地完成这个这个游戏。
这些指令将在输入格式中详述。
假设这款游戏一共有 T个关卡现在 Kiana 想知道对于每一个关卡至少需要发射多少只小鸟才能消灭所有的小猪。
由于她不会算所以希望由你告诉她。
注意:本题除 NOIP 原数据外还包含加强数据。
输入格式
第一行包含一个正整数 T表示游戏的关卡总数。
下面依次输入这 T 个关卡的信息。
每个关卡第一行包含两个非负整数 n,m分别表示该关卡中的小猪数量和 Kiana 输入的神秘指令类型。
接下来的 n 行中第 i 行包含两个正实数 (xi,yi)表示第 i 只小猪坐标为 (xi,yi)数据保证同一个关卡中不存在两只坐标完全相同的小猪。
如果 m0表示 Kiana 输入了一个没有任何作用的指令。
如果 m1则这个关卡将会满足至多用 ⌈n/31⌉ 只小鸟即可消灭所有小猪。
如果 m2则这个关卡将会满足一定存在一种最优解其中有一只小鸟消灭了至少 ⌊n/3⌋ 只小猪。
保证 1≤n≤180≤m≤20xi,yi10输入中的实数均保留到小数点后两位。
上文中符号 ⌈c⌉ 和 ⌊c⌋ 分别表示对 c 向上取整和向下取整例如 ⌈2.1⌉⌈2.9⌉⌈3.0⌉⌊3.0⌋⌊3.1⌋⌊3.9⌋3。
输出格式
对每个关卡依次输出一行答案。
输出的每一行包含一个正整数表示相应的关卡中消灭所有小猪最少需要的小鸟数量。
数据范围 输入样例
2
2 0
1.00 3.00
3.00 3.00
5 2
1.00 5.00
2.00 8.00
3.00 9.00
4.00 8.00
5.00 5.00输出样例
1
1 首先m没用 爆搜的思想是传进来一个状态找到没被覆盖的一个点枚举能覆盖这个点的抛物线再搜新状态 这里状压是对爆搜的优化
path[i][j]表示经过i、j两点的抛物线经过了哪些点
f[i]表示爆搜传进来的状态返回的值
对dp过程中只搜一个点而不是搜所有未被覆盖的点的解释
四个点如果最优解是选12和34如果先选12会先更新成1100走到1100时再更新成1111如果先选34会先更新成0011走到0011时再更新成1111更新的顺序与结果无关不管选哪个点都不会影响状态的遍历 而且一定是由小值更新大值的
这样复杂度会在原来的基础上乘以一个
#includebits/stdc.h
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl \nusing namespace std;typedef pairint, int PII;
typedef long long ll;
typedef pairdouble, double PDD;const int N 18, M 1 18;
const double eps 1e-6;int n, m;
int f[M];
int path[N][N];//i j两个点之间经过哪些点
PDD dot[N];int cmp(double x, double y)
{if(fabs(x - y) eps)return 0;if(x y)return -1;return 1;
}void solve()
{cin n m;memset(path, 0, sizeof path);memset(f, 0x3f, sizeof f);f[0] 0;for(int i 0; i n; i ){cin dot[i].first dot[i].second;}//处理pathfor(int i 0; i n; i ){path[i][i] 1 i;for(int j 0; j n; j ){double x1 dot[i].first, y1 dot[i].second;double x2 dot[j].first, y2 dot[j].second;if(!cmp(x1, x2))continue;//不能横坐标相等 double a (y1 / x1 - y2 / x2) / (x1 - x2);double b y1 / x1 - a * x1;if(a 0)continue;//抛物线要开口向下 int state 0;for(int k 0; k n; k ){double x dot[k].first, y dot[k].second;if(!cmp(a * x * x b * x, y)){state 1 k;}} path[i][j] state;}} for(int i 0; i 1 1 n; i ){int x -1;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;
}int main()
{IOSint _;cin _;while(_ --){solve();}return 0;
}
宝藏
参与考古挖掘的小明得到了一份藏宝图藏宝图上标出了 n 个深埋在地下的宝藏屋也给出了这 n 个宝藏屋之间可供开发的 m 条道路和它们的长度。
小明决心亲自前往挖掘所有宝藏屋中的宝藏。
但是每个宝藏屋距离地面都很远也就是说从地面打通一条到某个宝藏屋的道路是很困难的而开发宝藏屋之间的道路则相对容易很多。
小明的决心感动了考古挖掘的赞助商赞助商决定免费赞助他打通一条从地面到某个宝藏屋的通道通往哪个宝藏屋则由小明来决定。
在此基础上小明还需要考虑如何开凿宝藏屋之间的道路。
已经开凿出的道路可以任意通行不消耗代价。
每开凿出一条新道路小明就会与考古队一起挖掘出由该条道路所能到达的宝藏屋的宝藏。
另外小明不想开发无用道路即两个已经被挖掘过的宝藏屋之间的道路无需再开发。
新开发一条道路的代价是
这条道路的长度 ×× 从赞助商帮你打通的宝藏屋到这条道路起点的宝藏屋所经过的宝藏屋的数量包括赞助商帮你打通的宝藏屋和这条道路起点的宝藏屋。
请你编写程序为小明选定由赞助商打通的宝藏屋和之后开凿的道路使得工程总代价最小并输出这个最小值。
输入格式
第一行两个用空格分离的正整数 n 和 m代表宝藏屋的个数和道路数。
接下来 m 行每行三个用空格分离的正整数分别是由一条道路连接的两个宝藏屋的编号编号为 1∼n和这条道路的长度 v。
输出格式
输出共一行一个正整数表示最小的总代价。
数据范围
1≤n≤12, 0≤m≤1000, v≤5∗1e5
输入样例
4 5
1 2 1
1 3 3
1 4 1
2 3 4
3 4 1 输出样例
4 朴素dp有三维dp[i][j][k],第一维是整体的状态(有哪些点),第二维是最后一层的状态第三维是倒数第二层的状态。但这样时间复杂度和空间复杂度过于爆炸不能这样。 最后一层只能连向最后一层的限制我们可以换成最后一层可以连上上面任意一层乘的那个层数不变设前者状态为A,后者状态为B
B能取到的点范围大于A所以能去到的最小值也会A所以最终结果min(A)min(B)
B最后的结果肯定是一颗树的形式以下图为例设最小的形式是这个假设3能取到的最小的点不在倒数第二层而是在第一层也就是1层数k * 路长dd会变小乘积也会变小但如果3接到第二层就会变成 (k-1)*更小的那个d 乘积进一步变小说明这反而就不是最小值了就矛盾了所以假设不成立最小的点就在倒数第二层。而这个最终的状态是符合A的B的最小值在A之内得证min(A) min(B);
min(A)min(B)的同时min(A)min(B),证得min(A) min(B)。
但只是计算最小值可以这样。 说得简单点就是emm还是以上图为例比如3最合适的是连1应当连在第二层但现在连在了第三层距离乘了2如果连到第二层的话会乘1这个乘1绝对是符合A状态的乘2虽然不符合A状态但他的值绝对是大于等于那个乘1的两种情况都会枚举到所以无所谓只要包含了那个最小值就行。怎么说呢就是那种散弹枪开一百枪有一枪打得中就ok
#includebits/stdc.h
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl \nusing namespace std;typedef pairint, int PII;
typedef long long ll;const int N 12, M 1 12, INF 0x3f3f3f3f;int n, m;
int f[M][N];//整体状态为i,层数为j 第0层也算一层
int d[N][N], g[N][M];//点i到状态j的最短距离 int main()
{IOScin n m;memset(d, 0x3f, sizeof d);for(int i 0; i m; i ){int a, b, c;cin a b c;a --, b --;d[a][b] d[b][a] min(d[a][b], c);}memset(g, 0x3f, sizeof g);for(int i 0; i n; i ){for(int j 1; j 1 n; j ){for(int k 0; k n; k ){if(j k 1){g[i][j] min(g[i][j], d[i][k]);}}}}memset(f, 0x3f, sizeof f);for(int i 0; i n; i ){f[1 i][0] 0;}for(int i 1; i 1 n; i ){for(int j i - 1 i; j; j j - 1 i)//枚举i的子集 {int r i ^ j, cost 0;for(int k 0; k n; k ){if(j k 1){cost g[k][r];if(cost INF)break;}}if(cost INF)continue;for(int k 1; k n; k ){if((ll)cost * k INF)break;f[i][k] min(f[i][k], f[r][k - 1] cost * k);}}}int ans INF;for(int i 0; i n; i ){ans min(ans, f[(1 n) - 1][i]);}cout ans;return 0;
}
