本文主要是介绍jnu第一大混子的训练纪录4：基础练习题：搜索与贪心，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Minimum Scalar Product
大意：有两个数组a，b，允许随意交换数组内的顺序，求a1*b1+a2*b2…an*bn的最小值
解题：隐约感觉到如果一个降序，一个升序这样乘起来就是正确答案，事实确实如此，下面给证明
当n=2时，假设a已经排序（升序），则比较a1*b1+a2*b2 ①和a1*b2+a2*b1 ②的大小：
①-② = (a1-a2)*(b1-b2)，令b1≥b2即可得到 ① ≤ ②
当n>2时，如果b不是按降序排列，则存在i＜j使得bi＜bj，则由n=2可知交换bi和bj得到了更小的内积，因此b就一定是降序排列，使得不存在i＜j使bi＜bj。
注意最后结果可能超出int
crazy rows
给出一个只由0，1组成的矩阵，并只准交换相邻两行，求最少需要几次交换可以把矩阵变成下三角矩阵（右上角全是0）,保证输入的矩阵一定能在有限次交换后变成下三角矩阵
范围：N（长和宽）≤40
解题：在这个范围下尝试所有的交换方案N！显然是行不通的，于是有以下策略：
1.自上而下地得到下三角矩阵
2.找到可以放到第i行的行，选择最近的进行交换 （i=0，i++）
解释：为什么要自上而下地进行？因为下三角矩阵的特性，上面的行可以兼容下面的行，反之不行，所以有多个满足条件的行当然选择最近的，反正剩下的行可以满足之后的需求。
另外，先处理出每一行最后出现1的位置，可以把整体复杂度由N^3降到N^2
代码略
Bribe the Prisoners
大意：有一个监狱有并排着的p个牢房（数组）,现在要释放一些囚犯，每次释放一个囚犯时，相邻的囚犯会因为不公平而暴动，为了防止暴动需要给相邻的囚犯一枚金币贿赂，但是隔壁的隔壁也会发现这个消息并准备暴动，所以他们也需要给一枚金币贿赂，以此类推直到遇到空牢房（已经被释放过的）或者到监狱两边。现在要释放q名囚犯（随机给），q≤p，问以什么顺序释放所需金币最少，最少是多少？
解题思路：观察释放的过程，发现每当释放一个犯人后，牢房就分成了不影响的两块，不影响之后的问题，因此考虑使用DP。从最小的子问题开始，组合成大问题。从最后的状态开始推，即释放一名犯人所需最少金币数，释放两名。。。具体思路：csdn
Millionaire
难点：连续性问题，每轮压多少钱都是未知的，不知道怎么搜索。
但是可以考虑最后一轮的情况：
如果持有超过100w元，直接拿回家；超过50w元钱：全压上，至于为什么全压，是因为反正是最后一轮，输了拿不回家，不如全压了赢了就能拿回来（所谓的最优）;不超过50w元：一定不能拿回家了。
最后两轮的情况：
超过100w元，直接拿回；超过75w元，压上到100w的差值，如果赢了直接拿走，输了就进入下一轮50w的挡位，两次都输才会输，所以赢得概率是1-（1-p）^2；超过50w，全压，赢的概率为p；超过25w，必须连续赢两次，概率是p*p
n次赌博对应着2^n+1种状态，且前后两轮有明显的迭代性，考虑使用DP：设
dp[i][j] 表示第i轮赌博时，手中持有的钱数为第j阶段的采取最优策略后带钱回家的概率
状态转移方程：
dp[i+1][j] = max(P*dp[i][j+k]+(1-P)*dp[i][j-k]) 其中 0<=k<=min(j,n-j),n为依据赌博次数定下的总阶段数
对于上述等式的理解，我们第i+1场赌博中所持金钱在第j阶段的带钱回家最大概率是第i场赌博中手中所持金钱在j阶段之前的情况中我们赌赢了，即P*dp[i][j+k]的概率加上第i场赌博中我们输了，但存在如果所持金钱在j-k阶段时满足带钱回家的概率，即(1-P)*dp[i][j-k] ，其实就是这轮赢了，下一轮加上这轮赢得钱之后得阶段的胜率加上这轮失败了，减去这轮赢得钱之后的阶段的胜率加起来
int M,X;
double P;
double dp[2][(1 << MAX_M) + 1];//由于每个状态都是由上一个状态推知，所以可以用滚动数组/一维数组
int main(){int n = 1 << M;//总阶段数double *pre = dp[0],*nxt = dp[1];memset(pre,0,sizeof(double) * (n + 1));pre[n] = 1.0;//最大的阶段，即超过100w的胜率总是1for(int r = 0;r < M;r++){//每一轮的赌博枚举for(int i = 0;i <= n;i++){//每个阶段的枚举int jub = min(i,n - i);//jub是每轮要移动的阶段，不会超过一半阶段（全压）double t = 0.0;for(int j = 0;j <= jub;j++)//对移动的阶段枚举，对应压钱的多少t = max(t,pre[i + j] * P + pre[i - j] * (1 - P));//解释过了nxt[i] = t;}swap(pre,nxt);}int i = (LL)X * n / 1000000;//在哪个阶段printf("%.6f\n",pre[i]);return 0;}
以下为对之前学习的内容的分类练习题
2.1：基础的搜随
dfs
poj1979
dfs模板，连回溯都不用的那种
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<iomanip>
using namespace std;
typedef long long ll;
const long long ll_inf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const double pi=acos(-1.0);
const int Mod=1e9+7;
const int Max=30;
//cout<<setw(8)<<fixed<<setprecision(3);
//ios::sync_with_stdio(false);
char Map[Max][Max];
int flag[Max][Max];
int W,H;
int d[4][2]={{1,0},{0,1},{0,-1},{-1,0}};
int ans;
void dfs(int x,int y){for(int i=0;i<4;i++){int dx=x+d[i][0];int dy=y+d[i][1];if(dx>=0&&dy>=0&&dx<H&&dy<W&&Map[dx][dy]=='.'&&flag[dx][dy]==0){ans++;flag[dx][dy]=1;dfs(dx,dy);}}
}
int main(){while(1){ scanf("%d %d",&W,&H);if(W==0&&H==0)break;int x,y;getchar();for(int i=0;i<H;i++){for(int j=0;j<W;j++){scanf("%c",&Map[i][j]);if(Map[i][j]=='@')x=i,y=j;}getchar();}memset(flag,0,sizeof(flag));flag[x][y]=1;ans=0;dfs(x,y);ans++;printf("%d\n",ans);}return 0;
}水题的存在意义就是看你基础扎不扎实，基础代码写的快，少出错，一次过才能攀登高峰！
另外别用fflush（stidin）代替getchar，会re。。。我也不知道为什么
aoj0033
还有这么个aoj，除了是日语其他体验还挺好的
题意：随机给一个1-10的排列，判断能不能分成两组升序的组
我看网上的暴力dfs是搜索所有的状态，稍微过了点，归到dfs比较勉强，可以用两个数作为两个组的目前最大的数子，不断更新即可
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<iomanip>
using namespace std;
typedef long long ll;
const long long ll_inf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const double pi=acos(-1.0);
const int Mod=1e9+7;
const int Max=30;
//cout<<setw(8)<<fixed<<setprecision(3);
//ios::sync_with_stdio(false);
int main(){int t;cin>>t;while(t--){int a[10],a1,b1;for(int i=0;i<10;i++){cin>>a[i];}a1=a[0];int flag=1,flag1=1;for(int i=1;i<10;i++){if(a[i]<a1){if(flag){b1=a[i];flag=0;}else{if(a[i]<b1)flag1=0;else{b1=a[i];//更新b1 }}}elsea1=a[i];//更新a1 }if(flag1)cout<<"YES";elsecout<<"NO";cout<<'\n';}
}这网站，最后不输出空行反而不给过。。
aoj0118
题意：给一个用符号组成的图，相同的且相邻的（上下左右）符号组成一组，问一共有几组（相同符号不相邻算两组）
思路：对图的每一个元素都dfs一次，每次dfs标记这个连通块，每遇到没有标记的答案++即可
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<iomanip>
using namespace std;
typedef long long ll;
const long long ll_inf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const double pi=acos(-1.0);
const int Mod=1e9+7;
const int Max=120;
//cout<<setw(8)<<fixed<<setprecision(3);
//ios::sync_with_stdio(false);
char Map[Max][Max];
int flag[Max][Max];
int W,H;
int d[4][2]={{1,0},{0,1},{0,-1},{-1,0}};//下，右，左，上
int ans;
void dfs(int x,int y,char a){if(flag[x][y])return ;flag[x][y]=1;for(int i=0;i<4;i++){int dx=x+d[i][0];int dy=y+d[i][1];if(dx>=0&&dy>=0&&dx<W&&dy<H&&flag[dx][dy]==0){if(Map[dx][dy]==a){dfs(dx,dy,a);}}}
}
int main(){while(1){ scanf("%d %d",&W,&H);//给出w行 if(W==0&&H==0)break;getchar();for(int i=0;i<W;i++){for(int j=0;j<H;j++){scanf("%c",&Map[i][j]);}getchar();}memset(flag,0,sizeof(flag));ans=0;for(int i=0;i<W;i++){for(int j=0;j<H;j++){if(flag[i][j]==0){dfs(i,j,Map[i][j]);ans++;}}} printf("%d\n",ans);}return 0;
}poj3009
题目大意：很像小时候在挪鸡鸭上面玩的一个小游戏：打冰壶。每次可以选择一个方向推冰壶，冰壶会沿着这个方向一直滑，直到碰到障碍或者掉下悬崖（失败）。碰到障碍物后会停下并击碎障碍物。给出地图和冰壶的位置以及终点，问10步以内能不能把冰壶打到终点去（碰到终点就算胜利，不用考虑碰到后掉下去）。
思路：带回溯的dfs，如果没有滑动的设定就很简单了，对于滑动的处理，其他的解法一般是在dfs内部循环处理，而我是比较传统的一步一步来的dfs，多加了一些判断的条件，详情间代码
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<iomanip>
using namespace std;
typedef long long ll;
const long long ll_inf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const double pi=acos(-1.0);
const int Mod=1e9+7;
const int Max=30;
//cout<<setw(8)<<fixed<<setprecision(3);
//ios::sync_with_stdio(false);
int Map[Max][Max];
int W,H;
int d[5][2]={{1,0},{0,1},{0,-1},{-1,0},{0,0}};
int ans;
void dfs(int x,int y,int step,int p){if(step>=11)return ;if(x<0||y<0||x>=H||y>=W)//出界了 return ;else if(Map[x][y]==0&&p!=4){//是滑过来的 dfs(x+d[p][0],y+d[p][1],step,p); }else if(Map[x][y]==1||(Map[x][y]==0&&p==4)){//撞上了或者开局的时候 Map[x][y]=0;x-=d[p][0];y-=d[p][1];//回去一格for(int i=0;i<4;i++){//0:下 1：右 2：左 3：上 4:初始或者撞上了 int dx=x+d[i][0];int dy=y+d[i][1];if(dx>=0&&dy>=0&&dx<H&&dy<W&&Map[dx][dy]!=1){dfs(dx,dy,step+1,i);}}Map[x+d[p][0]][y+d[p][1]]=1; }else if(Map[x][y]==3){if(ans>step)ans=step;return;}}
int main(){while(1){ scanf("%d %d",&W,&H);//h行 if(W==0&&H==0)break;int sx,sy,gx,gy;getchar();for(int i=0;i<H;i++){for(int j=0;j<W;j++){scanf("%d",&Map[i][j]);if(Map[i][j]==2)sx=i,sy=j,Map[i][j]=0;else if(Map[i][j]==3)gx=i,gy=j;}}ans=11;//cout<<sx<<sy;dfs(sx,sy,0,4);if(ans<=10)printf("%d\n",ans);elseprintf("-1\n");}return 0;
}这样写思路比较清晰，但是回溯的部分卡到我了，因为我这样写在dfs到障碍后才让障碍消失，后面回溯起来就需要放在dfs的外面而不是里面，如果在里面的话意思就是一个方向结束了就把障碍回溯，实际上应该是几个方向都搜索完了才结束。这里写法就不如循环来的清晰了
bfs
aoj0558
题目大意：在 H * W 的地图里有 N 个工厂，每个工厂分别生产硬度为1-N 的奶酪，有一只老鼠准备把所有奶酪都吃完。老鼠的初始体力值为1，每吃一个奶酪体力值加 1。已知老鼠不能吃硬度大于当前体力值的奶酪，老鼠只能向上下左右四个方向走，求吃完所有奶酪老鼠需要经过的最小步数。已知老鼠可以吃到所有奶酪
思路：用bfs很容易求出起点到终点的最小步数。初始时，求起点到硬度值为 1 的奶酪的最小步数；接着将起点重置为此位置，继续求此位置到达硬度值为 2 的奶酪；如此类推。做N 次广度优先搜索，并累计其值即可。
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<iomanip>
using namespace std;
typedef long long ll;
const long long ll_inf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const double pi=acos(-1.0);
const int Mod=1e9+7;
const int Max=1010;
//cout<<setw(8)<<fixed<<setprecision(3);
//ios::sync_with_stdio(false);
int sx,sy;
int H,W,N;
int d[4][2]={{1,0},{0,1},{0,-1},{-1,0}};
char Map[Max][Max];
int vis[Max][Max];
struct node{int x,y,step;node(int xx,int yy,int s):x(xx),y(yy),step(s){}
};
int bfs(int a){int ans;memset(vis,0,sizeof(vis));queue<node>q;q.push(node(sx,sy,0));vis[sx][sy]=1;while(!q.empty()){node s=q.front();q.pop();if(Map[s.x][s.y]==a+'0'){sx=s.x;sy=s.y;ans=s.step;break;}for(int i=0;i<4;i++){int dx=s.x+d[i][0];int dy=s.y+d[i][1];if(dx>=0&&dx<H&&dy>=0&&dy<W&&Map[dx][dy]!='X'&&!vis[dx][dy]){vis[dx][dy]=1;q.push(node(dx,dy,s.step+1));}}}return ans;
}
int main(){cin>>H>>W>>N;for(int i=0;i<H;i++){for(int j=0;j<W;j++){cin>>Map[i][j];if(Map[i][j]=='S'){sx=i;sy=j;}}}int ans=0;for(int i=1;i<=N;i++){ans+=bfs(i);}printf("%d\n",ans);
}可作为bfs模板使用
aoj0121
题意：给出由0-7排列组成的2*4的长方形，每次0可以和上下左右的数字交换（如果有的话），问最少多少步能排列成0123/4567，保证一定能排列成给出的顺序。
思路：求最短路径，考虑使用bfs求解，但是难点是：以0为目标每次移动会产生两个状态，每个状态如果用数组存肯定是超内存的，并且对于每个输入都bfs一遍肯定会超时，于是可以逆向思维以下，既然保证一定能得到答案，那么就可以先对答案进行bfs求出所有状态的最少步数然后对每个输入查表就可以了，另外因为数组是固定的，为了查表方便/存储简洁，采用字符串的方式保存这个2*4的长方形，用map的方式保存每个字符串（就是输入的排列）的最少步数。
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<iomanip>
using namespace std;
typedef long long ll;
const long long ll_inf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const double pi=acos(-1.0);
const int Mod=1e9+7;
const int Max=1010;
//cout<<setw(8)<<fixed<<setprecision(3);
//ios::sync_with_stdio(false);
int d[4]={1,-1,4,-4};
map<string,int> dp;
void bfs(){queue<string>q;q.push("01234567");dp["01234567"]=0;while(!q.empty()){string s=q.front();q.pop();int pos=0;//pos是0的位置 for(int i=0;i<8;i++){if(s[i]=='0'){pos=i;break;}}for(int i=0;i<4;i++){int dx=pos+d[i];if(dx>=0&&dx<8&&!(pos==3&&i==0)&&!(pos==4&&i==1)){//长方形的左上角和右下角需要特殊判断 string temp=s;swap(temp[pos],temp[dx]);if(dp.find(temp)==dp.end()){dp[temp]=dp[s]+1;q.push(temp);} }}}
}
int main(){bfs();string s;while(getline(cin,s)){s.erase(remove(s.begin(),s.end(),' '),s.end());cout<<dp[s]<<endl;}return 0;
}由于bfs的特性，只要map里面没有这个字符串，那么第一次得到这个字符串的步数就一定是最短的。另外还要注意用字符串保存长方形的时候右上角和左下角的移动是受限制的。
对于map有查找函数find，查找方式为 map.find(map.first)==map.end()
这个输入是抄借鉴的，好强，删除所有的指定字符
s.erase(remove(s.begin(),s.end(),' '),s.end());
poj3669
题目：贝西听说一场不同寻常的流星雨即将来临；据报道，这些流星将撞击地球，摧毁它们撞击到的任何东西。出于对自身安全的担忧，她发誓要找到一个安全的地方（一个从未被流星摧毁的地方）。她目前正在坐标平面的原点吃草，希望移动到一个新的、更安全的位置，同时避免被沿途的流星摧毁。
报告说，有m颗流星将在时间Ti打击点（Xi，Yi） 每颗流星都会摧毁它撞击的点以及四个相邻的直线点阵点。
贝西在时间0离开原点，可以在第一象限内以每秒一个距离单位的速度平行于轴线移动到任何尚未被流星摧毁的相邻直线点（通常为4个）。她在任何时间都不能被定位在大于或等于被摧毁时间的点上）。
确定贝西到达安全地点的最短时间。
思路：时间对应距离，即找到安全坐标的最小距离，可以使用bfs，难点在于地图是变化的，不同时间对应地图会有不同的障碍不能走，肯定不能在bfs时更新地图，所以考虑转化成静态的地图。可以把每个陨石摧毁的时间直接标在地图上，当主人公的step（也是时间）小于当前所在的点的摧毁时间（即还没被摧毁）就是安全的，这样就得到一个判断下一步是否能走的条件。注意每个点的摧毁时间应取最早被摧毁的时间
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<iomanip>
using namespace std;
typedef long long ll;
const long long ll_inf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const double pi=acos(-1.0);
const int Mod=1e9+7;
const int Max=400;
//cout<<setw(8)<<fixed<<setprecision(3);
//ios::sync_with_stdio(false);
int t;
int d[5][2]={{1,0},{0,1},{0,-1},{-1,0},{0,0}};
int Map[Max][Max];
int vis[Max][Max];
struct node{int x,y,step;node(int xx,int yy,int s):x(xx),y(yy),step(s){}
};
int bfs(){int ans,flag=0;memset(vis,0,sizeof(vis));queue<node>q;q.push(node(0,0,0));vis[0][0]=1;while(!q.empty()){node s=q.front();// cout<<s.x<<' '<<s.y<<' '<<s.step<<'\n';q.pop();if(Map[s.x][s.y]==-1){//逃到了安全的地方 ans=s.step;flag=1;break;}for(int i=0;i<4;i++){int dx=s.x+d[i][0];int dy=s.y+d[i][1];if(dx>=0&&dy>=0&&(Map[dx][dy]>s.step+1||Map[dx][dy]==-1)&&!vis[dx][dy]){vis[dx][dy]=1;q.push(node(dx,dy,s.step+1));}}}if(flag)return ans;else return -1;
}
int main(){cin>>t;int a,b,c;memset(Map,-1,sizeof(Map));for(int i=0;i<t;i++){cin>>a>>b>>c;for(int i=0;i<5;i++){int dx=a+d[i][0];int dy=b+d[i][1];if(dx>=0&&dy>=0){if(Map[dx][dy]==-1)Map[dx][dy]=c;else{if(c<Map[dx][dy]){Map[dx][dy]=c;//用最早的时间 }}}}}printf("%d\n",bfs());
}穷竭搜索
poj2718
题意：给一些数字，求这些数字随意组合形成的两个新数字的最小的差值的绝对值。
思路：真的就是求所有组合然后不断更新最小值，主要是输入的技巧性和求组合的技巧性
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<iomanip>
using namespace std;
typedef long long ll;
const long long ll_inf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const double pi=acos(-1.0);
const int Mod=1e9+7;
const int Max=1010;
//cout<<setw(8)<<fixed<<setprecision(3);
//ios::sync_with_stdio(false);
int n;
string in;
int num[10];
int main(){cin>>n;getchar();while(n--){int i=0;int ans=inf;getline(cin,in);for(int j=0;j<in.size();j++) if(in[j]>='0'&&in[j]<='9')num[i++]=in[j]-'0';do{if(num[0]==0||num[i/2]==0) continue;int a=0,b= 0;for(int j=0;j<i/2;j++){a=a*10+num[j];}for(int j=i/2;j<i;j++){b=b*10+num[j];}ans=min(ans,(int)abs(a-b));}while(next_permutation(num,num+i));printf("%d\n",ans);}
}输入没有规定长度和数量（最多10个），用getline()读入一行然后处理。求数字的组合直接用系统的next_permutation函数，数字很少完全可以直接暴力搜全部的
poj3187
题目大意：有数字1~n的排列组合，以杨辉三角的形式得到最终的和，现在告诉你最终的和以及n，求最初的排列，如有多解则输出字典序最小的哪个
思路：排列组合，还是字典序最小，字里行间都想说next_permutation，然后直接求杨辉三角就行
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<iomanip>
using namespace std;
typedef long long ll;
const long long ll_inf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const double pi=acos(-1.0);
const int Mod=1e9+7;
const int Max=1010;
//cout<<setw(8)<<fixed<<setprecision(3);
//ios::sync_with_stdio(false);
using namespace std;int main(){int n,m;cin>>n>>m;int s[10];int a[10][10];for(int i=1;i<=n;i++) s[i-1]=i;do{for(int i=0;i<n;i++){a[0][i]=s[i];} for(int i=1;i<n;i++){for(int j=0;j<n-i;j++){a[i][j]=a[i-1][j]+a[i-1][j+1];}}if(b==m){for(int i=0;i<n;i++){cout<<s[i]<<' ';}break;}}while(next_permutation(s,s+n));
}poj3050
题意：给出一个由数字组成的5*5网格，可以从任意点出发向上下左右走5步，得到一个6位数的数字（可能有前导零），问能得到多少个数字
思路：用dfs深搜即可，虽然不知道为什么放在穷竭搜索这里，最后得到的数字用set集合储存比较方便
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<iomanip>
using namespace std;
typedef long long ll;
const long long ll_inf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const double pi=acos(-1.0);
const int Mod=1e9+7;
const int Max=5;
//cout<<setw(8)<<fixed<<setprecision(3);
//ios::sync_with_stdio(false);
using namespace std;
int Map[Max][Max];
int flag[Max][Max];
int W,H;
int d[4][2]={{1,0},{0,1},{0,-1},{-1,0}};
int ans;
set<int>s;
void dfs(int x,int y,int step,int ans){if(step==6){s.insert(ans);return ;}for(int i=0;i<4;i++){int dx=x+d[i][0];int dy=y+d[i][1];if(dx>=0&&dy>=0&&dx<5&&dy<5){int t=ans*10+Map[dx][dy];dfs(dx,dy,step+1,t);}}
}
int main(){for(int i=0;i<5;i++){for(int j=0;j<5;j++){cin>>Map[i][j];} }for(int i=0;i<5;i++){for(int j=0;j<5;j++){dfs(i,j,0,0);} }cout<<s.size();
}aoj0525
题意：给出一个n行m列的01网格，可以对任意行，列做一次操作使这一列的0变1，1变0，问最后最多能得到多少个1，其中0<n<10，0<m<1w
思路：对于这种题一般都是要把全部状态都找出来的，根据行和列的数据范围，可以确定搜索对象为行，最多有2^10=1024种可能，然后对于每种可能对列进行加和判断即可
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<iomanip>
using namespace std;
typedef long long ll;
const long long ll_inf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const double pi=acos(-1.0);
const int Mod=1e9+7;
const int Max=10005;
//cout<<setw(8)<<fixed<<setprecision(3);
//ios::sync_with_stdio(false);
int Map[15][Max];
int r,c;
int ans;
void dfs(int row,int flag){if(row==r){int sum1=0;for(int i=0;i<c;i++){int sum=0;for(int j=0;j<r;j++){sum+=Map[j][i];}sum1+=max(sum,r-sum);}ans=max(ans,sum1);return;}if(flag){for(int j=0;j<c;j++){if(Map[row][j])Map[row][j]=0;elseMap[row][j]=1;}dfs(row+1,1);dfs(row+1,0);for(int j=0;j<c;j++){if(Map[row][j])Map[row][j]=0;elseMap[row][j]=1;} }else{dfs(row+1,1);dfs(row+1,0); }}
int main(){while(1){ scanf("%d %d",&r,&c);if(r==0&&c==0)break;for(int i=0;i<r;i++){for(int j=0;j<c;j++){scanf("%d",&Map[i][j]);}}ans=0;dfs(0,1);//1翻 dfs(0,0);//0不翻 cout<<ans<<'\n';}return 0;
}日语题的翻译太阴间了
贪心
区间：
poj2376
题意：给出小区间和大区间，问最少需要多少小区间能组成大区间
思路：以每个小区间的开始时间排序，搜出可用区间中右端点最远的那个，更新右端点，重复操作直到区间用完或者右端点已经超过/达到大区间的右端点
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<iomanip>
using namespace std;
typedef long long ll;
const long long ll_inf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const double pi=acos(-1.0);
const int Mod=1e9+7;
const int Max=10005;
//cout<<setw(8)<<fixed<<setprecision(3);
//ios::sync_with_stdio(false);
int n,t;
struct cow{int start,end;int flag;
}a[25000];
bool cmp(cow a1,cow a2){return a1.start<a2.start;
}
int main(){scanf("%d %d",&n,&t);
// cin>>n>>t;for(int i=0;i<n;i++){scanf("%d %d",&a[i].start,&a[i].end);//cin>>a[i].start>>a[i].end;a[i].flag=0;}sort(a,a+n,cmp);int T=0,End=0,ch,ans=0;for(int i=0;i<n;){if(a[i].start>T+1){printf("-1");return 0; }while(a[i].start<=T+1&&i<n){if(a[i].end>End){End=a[i].end;ch=i; }i++;}T=a[ch].end;ans++;if(T>=t)break; }if(T<t)printf("-1");else printf("%d",ans);
}poj1328
题意：给出一个坐标系，给出一些岛屿，要求用一些在x轴上的半径为d的雷达罩住所有岛屿，问最少要多少雷达？
思路：首先，雷达是一个圆形，如果从左向右看岛屿的话，在雷达能覆盖岛屿的前提下，要想最大化利用雷达就应该尽量往右边靠。但是所以对于每个岛屿不记录它的坐标，而是纪录雷达能罩住它的左右位置，然后排序，如果雷达不能罩住当前岛屿就+1并更新雷达位置。这里有个易错的地方是岛屿应该按照左边界排序还是有边界排序，答案是左边界，考虑如果两个岛屿x坐标相同，一个在上面一个在下面，如果按右边界排序，就会在更新的时候跳过在上面的岛屿，而事实上雷达并没有包括这个岛屿。
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<iomanip>
using namespace std;
typedef long long ll;
const long long ll_inf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const double pi=acos(-1.0);
const int Mod=1e9+7;
const int Max=1005;
//cout<<setw(8)<<fixed<<setprecision(3);
//ios::sync_with_stdio(false);
struct node{double x,y;
}a[Max];
bool cmp(node a,node b){return a.y<b.y;
}
int Case=1;
int main(){int n,d;while(1){cin>>n>>d;if(n==0&&d==0)break;int flag=0;for(int i=0;i<n;i++){double x,y;cin>>x>>y;if(y>d||y<0){ flag=1;} double dis=sqrt(d*d-y*y);a[i].x=x-dis;a[i].y=x+dis;}if(flag){cout<<"Case "<<Case++<<": "<<"-1"<<'\n';continue;}sort(a,a+n,cmp);double r=a[0].y;int ans=1;for(int i=1;i<n;i++){if(a[i].x<=r)continue;else{r=a[i].y;ans++;}}cout<<"Case "<<Case++<<": "<<ans<<'\n';}
}另外注意记得开double
poj3190
题意：有N只牛要挤奶，每个牛圈只能同时让一只奶牛挤奶，每只奶牛只在特定的A到B时间段产奶，问至少需要几个牛圈。
思路：首先以开始A为关键词从小到大排序，保证遍历的时候都是取出开始时间最小的🐂，然后把🐂加入一个以B为关键词从小到大排序的优先队列，然后对每个🐂进行判断，如果比队首的时间长就可以共用一个牛圈，否则就多加一个牛圈。贪心的思路是让最先结束的时间得到充分利用，这样得到的牛圈一定是最少的。
lude<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<iomanip>
using namespace std;
typedef long long ll;
const long long ll_inf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const double pi=acos(-1.0);
const int Mod=1e9+7;
const int Max=50005;
//cout<<setw(8)<<fixed<<setprecision(3);
//ios::sync_with_stdio(false);
struct node{int start,end;int bh;bool operator < (const node& b)const{//结束时间早的在上面 return end>b.end;}
}cow[Max];
bool cmp(node a,node b){return a.start<b.start;
}
int main(){int n;scanf("%d",&n);//cin>>n;for(int i=0;i<n;i++){scanf("%d %d",&cow[i].start,&cow[i].end);cow[i].bh=i;}sort(cow,cow+n,cmp);//以结束时间排序priority_queue<node> c;int ans=1,lan[Max];c.push(cow[0]);lan[cow[0].bh]=1;for(int i=1;i<n;i++){node t=c.top();if(t.end+1<=cow[i].start){//不用分配栏lan[cow[i].bh]=lan[t.bh];c.pop();c.push(cow[i]);}else{ans++;lan[cow[i].bh]=ans;c.push(cow[i]);} }printf("%d\n",ans);for(int i=0;i<n;i++){printf("%d\n",lan[i]);}
} 容易看出队列中🐂的数量就是当前牛圈的数量，对不用新开牛圈的牛要进行更新，即pop再push一下就行了。还有这个运算符重载的内容我都忘了，又要去看一眼了
其他贪心
poj2393
题意：有一个工厂生产奶酪，每天都有不同的成本价和订单量，订单量必须当天完成，但是订单需要的奶酪可以提前生产，生产出来的奶酪可以存放在仓库中，仓库无限大并且奶酪不会坏（这不合理），每个奶酪每存一天要多给s元，现给出每天的价格和订单量以及s，问成本最少多少钱
思路：由贪心思路，要想成本最低，肯定选择单价比较低的那一天生产更多的奶酪，对于每天而言，要么今天生产完所有订单量，要么以前生产完订单量。（为什么是生产完订单量呢，假设之前生产一部分能节省成本那么生产完肯定能节省更多成本，反之亦然）但是还有s这个变量，如何比较什么时候生产成本最低呢，考察s这个量，如果存起来的话，每个奶酪每天需要多花s元，是不是刚好就可以算到成本上了呢，所以可以设一个当前最小的成本，每过一天就+s，然后比较现在的价格和这个最小量，大了就可以提前生产，小了就更新
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<iomanip>
using namespace std;
typedef long long ll;
const long long ll_inf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const double pi=acos(-1.0);
const int Mod=1e9+7;
const int Max=10005;
//cout<<setw(8)<<fixed<<setprecision(3);
//ios::sync_with_stdio(false);
int main(){int n,s;int a[Max][2];int flag[Max];memset(flag,0,sizeof(flag));scanf("%d %d",&n,&s);for(int i=0;i<n;i++){scanf("%d %d",&a[i][0],&a[i][1]);}ll ans=0;ans+=(ll)(a[0][0]*a[0][1]);int Min=a[0][0];for(int i=1;i<n;i++){Min+=s;if(Min<a[i][0]){ans+=(ll)(Min*a[i][1]);}else{Min=a[i][0];ans+=Min*a[i][1];}}printf("%lld\n",ans);
}
记得开longlong
poj1017
题意：有高为1，长宽相同的六种盒子：1*1，2*2，3*3....6*6，给出各自的数量，问最少能用多少个6*6的盒子装下左右的盒子
思路：分类讨论就行了，都算不上贪心，比如5*5的时候能放1*1的盒子5个
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<iomanip>
using namespace std;
typedef long long ll;
const long long ll_inf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const double pi=acos(-1.0);
const int Mod=1e9+7;
const int Max=10005;
//cout<<setw(8)<<fixed<<setprecision(3);
//ios::sync_with_stdio(false);
int main(){int s1,s2,s3,s4,s5,s6;while(cin>>s1>>s2>>s3>>s4>>s5>>s6&&(s1+s2+s3+s4+s5+s6)){int BoxNum=0; //放进所有盒子所需的最少箱子数BoxNum+=s6; //6*6的盒子，每个都刚好独占一个箱子BoxNum+=s5; //5*5的盒子，放进箱子后，每个箱子余下的空间只能放11个1*1的盒子s1=max(0,s1-s5*11); //把1*1的盒子尽可能地放进已放有一个5*5盒子的箱子BoxNum+=s4; //4*4的盒子，放进箱子后，每个箱子余下的空间为5个2*2的盒子空间//先把所有2*2的盒子尽可能地放进这些空间if(s2>=s4*5) //若2*2的盒子数比空间多s2-=s4*5; //则消去已放进空间的部分else //若2*2的盒子数比空间少{ //则先把所有2*2的盒子放进这些空间s1=max(0,s1-4*(s4*5-s2)); //再用1*1的盒子填充本应放2*2盒子的空间s2=0; //一个2*2空间可放4个1*1盒子}BoxNum+=(s3+3)/4; //每4个3*3的盒子完全独占一个箱子s3%=4; //3*3的盒子不足4个时，都放入一个箱子，剩余空间先放2*2，再放1*1if(s3){ //当箱子放了i个3*3盒子，剩下的空间最多放j个2*2盒子if(s2>=7-2*s3) //其中i={1,2,3} ; j={5,3,1} 由此可得到条件的关系式{s2-=7-2*s3;s1=max(0,s1-(8-s3)); //当箱子放了i个3*3盒子，并尽可能多地放了个2*2盒子后} //剩下的空间最多放j个1*1盒子，其中i={1,2,3} ; j={7,6,5}else //但当2*2的盒子数不足时，尽可能把1*1盒子放入剩余空间{ //一个箱子最多放36个1*1，一个3*3盒子空间最多放9个1*1，一个2*2盒子空间最多放4个1*1s1=max(0,s1-(36-9*s3-4*s2)); //由此很容易推出剩余空间能放多少个1*1s2=0;}}BoxNum+=(s2+8)/9; //每9个2*2的盒子完全独占一个箱子s2%=9; //2*2的盒子不足9个时，都放入一个箱子，剩余空间全放1*1if(s2)s1=max(0,s1-(36-4*s2));BoxNum+=(s1+35)/36; //每36个1*1的盒子完全独占一个箱子cout<<BoxNum<<endl;}return 0;
}这是别人的代码，自己写的虽然对但是太冗余，还有很多需要向别人学习，比如当3*3的盒子情况时，别人能用7-2*s3这种方式表示出来，我只能一个一个分情况。。。。
poj3040
题意：有不同的硬币（面值小的一定能被面值大的整除），每天要付出去s元，只能多付不能少付，给出各个硬币的值和数量，问最多能付多少天
思路：贪心1：因为小的一定能被面值大的整除，而小的更方便凑，所以能用大的就不用小的。 贪心2：为了能付更多天，能少浪费就少浪费 由这两个贪心思路，就可以直到对所有的硬币如何找到一种方法来付当天的硬币：首先，超过s的硬币可以直接付掉，然后，对硬币从大到小来凑s，注意这里不能超过s，然后从小到大凑s，这里可以超过s。这样用来“浪费”的硬币就是最小的。其他细节在程序中给出
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<iomanip>
using namespace std;
typedef long long ll;
const long long ll_inf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const double pi=acos(-1.0);
const int Mod=1e9+7;
const int Max=10005;
//cout<<setw(8)<<fixed<<setprecision(3);
//ios::sync_with_stdio(false);
struct coin{int val,num;
}a[Max];
bool cmp(coin a,coin b){return a.val>b.val;
}
int main(){int n,c;cin>>n>>c;for(int i=0;i<n;i++){cin>>a[i].val>>a[i].num;}sort(a,a+n,cmp);int ans=0;for(int i=0;i<n;i++){if(a[i].val>=c){//超过c的直接付掉ans+=a[i].num;a[i].num=0;}}while(true){//反复求凑的方法 int way[Max]={0},mm=inf,temp=0;//mm保存这种方法最多 多少次 for(int i=0;i<n;i++){if(a[i].num>0){way[i]=min((c-temp)/a[i].val,a[i].num);//用这种硬币多少个temp+=way[i]*a[i].val;//num还没减，先求方法if(way[i]!=0)mm=min(mm,a[i].num/way[i]);if(temp==c)break; }}if(temp==c){for(int i=0;i<n;i++){if(way[i]!=0)a[i].num-=mm*way[i];}ans+=mm;}else{//还需要凑for(int i=n-1;i>=0;i--){if(a[i].num-way[i]>0){//这里注意减去已经用的硬币 temp+=a[i].val;//只可能用一枚最小的硬币 way[i]++;mm=min(mm,a[i].num/way[i]);if(temp>=c){for(int i=0;i<n;i++){if(a[i].num>0)a[i].num-=mm*way[i];}ans+=mm;break;} }} }if(temp<c){//凑不齐了 break;}}cout<<ans<<'\n';
}poj1862
给出一些数字，每次操作可以取出两个数字a，b 然后把2*sqrt（a*b）放回去，问最后能剩下的最少的数字。
思路：由不等式a + b ≥ 2*sqrt（a*b）得到，要想留下最小的，就先把大的拿来用了就行了，最后留下小的
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<iomanip>
using namespace std;
typedef long long ll;
const long long ll_inf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const double pi=acos(-1.0);
const int Mod=1e9+7;
const int Max=10005;
//for(int i=0;i<n;i++)
//cout<<setw(8)<<fixed<<setprecision(3);
//ios::sync_with_stdio(false);
int main(){int n;cin>>n;priority_queue<double> q;for(int i=0;i<n;i++){double a;cin>>a;q.push(a);}while(q.size()!=1){double a,b;a=q.top();q.pop();b=q.top();q.pop();double c=2.0*sqrt(a*b);q.push(c);}cout<<fixed<<setprecision(3);cout<<q.top();
}poj3262
题意：不好描述自己点进去看
思路：以两头牛的情况：🐂a：t1，d1 ；🐂2：t2，d2 那么只需要比较t1*d2和t2d1就行了。多头牛的情况是一样的。
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<iomanip>
using namespace std;
typedef long long ll;
const long long ll_inf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const double pi=acos(-1.0);
const int Mod=1e9+7;
const int Max=100005;
//for(int i=0;i<n;i++)
//cout<<setw(8)<<fixed<<setprecision(3);
//ios::sync_with_stdio(false);
struct cow{int t,dis;
}a[Max];
bool cmp(cow a,cow b){return a.dis*b.t>b.dis*a.t;
}
int main(){int n;cin>>n;ll ans=0,sum=0;for(int i=0;i<n;i++){cin>>a[i].t>>a[i].dis;sum+=(ll)a[i].dis;}sort(a,a+n,cmp);for(int i=0;i<n-1;i++){sum-=(ll)a[i].dis;ans+=(ll)(sum*a[i].t*2);}cout<<ans<<'\n';
}这篇关于jnu第一大混子的训练纪录4：基础练习题：搜索与贪心的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
