网站什么时候做解析,网络推广的好处,可以在线观看的免费资源,新媒体营销策略都有哪些目录
今天知识点
dp每个票的使用情况#xff0c;然后更新此票状态下的最优解#xff0c;dp到没有票就行了
dp每行的种植状态#xff0c;从i-1行进行不断转移
dp每行的种植状态#xff0c;从i-1和i-2行进行不断转移
POJ2686马车旅行
思路#xff1a;
POJ3254 玉米田…目录
今天知识点
dp每个票的使用情况然后更新此票状态下的最优解dp到没有票就行了
dp每行的种植状态从i-1行进行不断转移
dp每行的种植状态从i-1和i-2行进行不断转移
POJ2686马车旅行
思路
POJ3254 玉米田
思路
POJ1185炮兵阵地
思路 前置知识
基于状态压缩下的集合操作1.空集: 0
2.只含有第i个元素的集合{i}: 1i
3.含有全部n个元素的集合{0,1,2,....,n-1}: (1n)-1
4.判断第i个元素是否属于集合S: if(Si1)
5.向集合中加入第i个元素S ∪ {i}: S|1i
6.从集合中除去第i个元素S - {i}: S~(1i)
7.集合S和T的并集S∪T: S | T
8.集合S和T的交集S∩T: S T POJ2686马车旅行
有一个公路网连接这些城市可以乘坐马车通行。乘坐马车需要一张票旅行者有许多车票每张票上都标记了马的数量马越多跑的越快。 你应该考虑如果使用这些票使得在最短时间内把旅行者从出发点他带到目的地的最佳路线。 假设一下条件 1.通过公路直接连接的两个城市之间只能使用一张车票且每张票只能用一次 2.乘马车的时间等于两城市之间的距离除以马的数量 3.忽略换乘所需的时间
输入 2 4 4 2 1 3 1 2 3 3 1 3 3 4 1 2 4 2 5 2 4 3 4 1 5 5 1 2 10 2 3 10 3 4 10 输出 3.667 impossible 思路
因为每跑一次票的状态就变动一次所以我们设置dp[s][u]表示达到当前u点且持有s车票的最小花费其中s是票的二进制状态。 状态转移从u到v当前点v的状态s一定最小的dp[s][u]dis/t转移过来其中ss~(1i) dp[s~(1i)][v]min(dp[s~(1i)][v],dp[s][u]dis[u][v]/t[i]) 转移顺序s从大到小因为大的状态必须要先于小的先确定下来所以s一定在最外层。然后是每个起点到每个终点使用每张票来去更新每个点也就是维护该状态下的最优解 #include bits/stdc.h
using namespace std;
const double inf0x3f3f3f3f;
double ans;
int n,m,p,a,b;
int t[20],dis[50][50];
double dp[110][32];//dp[s][u]表示达到当前u点且持有s车票的最小花费void solve(){for(int i0;i(1(n1));i)for(int j0;jm1;j)dp[i][j]inf;dp[(1n)-1][a]0;//起点状态ansinf;for(int s(1n)-1;s0;s--){//状态从大到小for(int u1;um;u)//遍历每个城市for(int i0;in;i)//遍历每种车票可用就用if((si)1)for(int v1;vm;v)//尾点城市if(dis[u][v]0){//如果能走就把第i张票置零dp[s~(1i)][v]min(dp[s~(1i)][v],dp[s][u](double)dis[u][v]/t[i]);}ansmin(ans,dp[s][b]);}}
int main(){while(cinnmpab){if(nmpab0)break;for(int i0;in;i){scanf(%d,t[i]);//每张车票的数量}memset(dis,-1,sizeof(dis));//初始化成无穷大也行for(int i0;ip;i){//p条变int u,v,w;scanf(%d%d%d,u,v,w);dis[u][v]dis[v][u]w;}solve();if(ansinf)printf(Impossible\n);else printf(%.3lf\n,ans);}
} POJ3254 玉米田
由m*n(m12,n12)的方格组成的玉米田要在这些方格上种上玉米有些方格是贫瘠的(0表示)有些是肥沃的(1表示)贫瘠的不能种植。 另外在种植的时候不能在相邻的方格种上玉米也就是不能共享边。问一共有多少种种植方案。
输入 2 3 1 1 1 0 1 0 思路
每一行的状态都和上一行的状态有关状态数有太多因此需要进行状态压缩 首先将每行的状态压缩成j的二进制状态。然后我们进行dp行设置dp[i][j]表示第i行的第j种状态时对应的前i行的方案数。转移方程dp[i][j](dp[i][j]dp[i-1][k])%mod; k是第i-1行所有的可行状态
在确定每行转移的时候都要考虑1.横向方案 2.横向方案是否和地图匹配 3.是否和i-1行冲突 存每行的可能状态相邻的两列不能都是1那就看xx1是不是0就是可能的横向方案是否和i-1冲突种表示1不种表示0 那么在判断两行合法性时不能出现有一列同1(两行都种)所以xy0是合法的存图肥沃我们用0表示贫瘠用1表示 那么判断此地和此种法合法性时不能出现同1(在贫瘠的地方种)所以xy0是合法的 如果不这样的话0和1与是0你就分不清了 【注意】外面每行i循环一次其次里面是第i行的每个状态j循环一次(找到合适的j)最后是第i-1行的每个状态k循环一次(找到每个合适的k)共O(n^3)
#include bits/stdc.h
using namespace std;
const int mod1e8;
int sta[600],top,n,m;
int dp[20][600],cur[20];bool check(int x){if(xx1)return 0;return 1;
} void init(){//预处理top0;for(int i0;i(1n);i){//记录所有的没有相邻1的种法if(check(i))sta[top]i;}
}void solve(){for(int j1;jtop;j){//处理第一行if(!(sta[j]cur[1])) dp[1][j]1;}for(int i2;im;i){//处理剩余行for(int j1;jtop;j){//sta[j]是第i行的每种种法if(sta[j]cur[i]) continue;//检测当前状态是否和当前行匹配for(int k1;ktop;k){//sta[k]是i-1行的每种法if(sta[k]cur[i-1])continue;//检测当前状态和当前行是否匹配if(sta[j]sta[k])continue;//第i行和第i-1行有冲突dp[i][j](dp[i][j]dp[i-1][k])%mod;}}}
}int main(){while(cinmn){//m是行n是列init();int num;memset(dp,0,sizeof(dp));for(int i1;im;i){cur[i]0;for(int j1;jn;j){scanf(%d,num);if(num0)cur[i](1(n-j));//读入地图 1变00变1}}solve();int ans0;for(int j1;jtop;j)ans(ansdp[m][j])%mod;//最后一行所有方案数加起来coutans;}
} POJ1185炮兵阵地
在N*M(N100,M10)的地图上布置炮兵H格子为山地不能布置P格子为平原可以布置。炮兵的攻击范围是沿横向左右各两格沿纵向上下个两格子 炮兵之间不能误伤。问在整个地图中最多能拜访多少个炮兵 5 4 PHPP PPHH PPPP PHPP PHHP 思路 首先要对行进行状态压缩(对列的话太大了枚举2^100还不如不压缩呢)我们每次确定行的状态都需要考虑1.横向方案 2.横向方案是否和地图匹配 3.是否和i-1行i-2行冲突
设置dp[i][j][k]表示第i行为第j状态第i-1行为第k状态时 对应的前i行放置的最大炮兵数。转移方程dp[i][j][k]max(dp[i][j][k],dp[i-1][k][t]num[j]);
j是第i行的方案k是第i-1行的方案t是i-2行的方案 存每行的可能状态左右相邻1个间隔和2个间隔都不能炮兵就是可能的横向方案存图(1,1)开始存。0表示平原1表示山地那么在放置的时候不能出现同1(在山地放炮兵)所以xy0是合法的保证合法的是0就行了是否冲突第i行和第i-1行第i-2行 不能出现有一列同1(两行都放炮兵)所以xy0是合法的 【注意】外面每行i循环一次其次里面是第i行的每个状态j循环一次(找到合适的j)然后是第i-1行的每个状态k循环一次(供第i行找到合适的k) 接着是第i-2行的每个状态t循环一次(供第i-1行找到合适的t)
#include bits/stdc.h
using namespace std;
int n,m,top;
char mp[110][20];
int num[70];
int stk[70],cur[70];//stk表示横向可能的方案cur是我们存的地图行
int dp[110][70][70];bool check(int x){if(x(x1))return 0;//相邻1间隔是否合法if(x(x2))return 0;//相邻2间隔是否合法return 1;
}void init(){//统计所有的可能合法状态最多60种top0;for(int i0;i(1m);i){if(check(i))stk[top]i;}
}int count(int x){//统计x二进制中1的个数int cnt0;while(x){if(x1)cnt;xx1;}
// while(x){//这个更快
// cnt;
// x(x-1);
// } return cnt;
}int solve(){int ans0;memset(dp,-1,sizeof(dp));for(int j0;jtop;j){//初始化第一行的状态num[j]count(stk[j]);if(!(stk[j]cur[1])){//和地图匹配dp[1][j][0]num[j];//第一行状态为j上一行状态为0知道为啥从(1,1)开始初始化了把ansmax(ans,dp[1][j][0]);}}for(int i2;in;i){//处理每一行for(int j0;jtop;j){//遍历第i行的可能方案if(stk[j]cur[i])continue;//是否和地图匹配for(int k0;ktop;k){//遍历第i-1行的可能方案if(stk[j]stk[k])continue;//此行和上一行是否匹配不用再判断和地图是否匹配不匹配dp是-1不影响的for(int t0;ttop;t){//遍历上二行可能方案if(stk[j]stk[t])continue;//此行和上二行是否匹配dp[i][j][k]max(dp[i][j][k],dp[i-1][k][t]num[j]);}if(in)ansmax(ans,dp[i][j][k]);//不要放在外面套3个for取max}}}return ans;
}
int main(){while(cinnm){init();for(int i1;in;i){scanf(%s,mp[i]1);//加1是为了从1下标开始存}for(int i1;in;i){cur[i]0;for(int j1;jm;j){if(mp[i][j]H)//同样的不能放的地方存1cur[i](1(m-j));}}coutsolve();}
}
