[题解]机器分配 原题链 解题思路： DP, f表示前个公司分配台机器所取得的最大利润。当前的最大利润为：前个公司分配台机器所取得的最大利润加上当前第个公司分配台机器所取得的利润的总和，与之前取得的最大利润的较大值。所以可以得出: maxx = max(ans[i - 1][k] + value[i][j - k],maxx); a[i][j] = maxx; ---------------------------分析完毕-------------------------- 源代码 #include <bits/stdc++.h> using namespace std; int ...

[题解]关押罪犯 原题链 主要算法：并查集 主要思路： 先用结构体将每一对罪犯的怨气值储存，再用怨气值为关键词从大到小排序。现在，为了让事情的影响最小，我们需要让怨气值最大的一对罪犯不在同一个监狱，所以在从大到小的顺序合并的时候是: merge(a[i].x,a[i].y + n); merge(a[i].y,a[i].x + n) 那么，如果在一次合并时，我们发现有两个我们将要合并的人已经在另一个集合里了时就可以输出这时的罪犯的怨气值及时结果。因为我们是从怨气值最大的时候往后操作，那么如果我们要将两个罪犯重新拆开重新合并的话，时间的影响值就会增加， 答案就不能保证最优。 源代码 #inclu...

[题解]分油问题 算法：广搜 解题思路： 因为要求最少的变换次数，所以很自然的想到要用广搜。广搜的初始状态为:10L的瓶子装满，其他的瓶子为空，接着只需要进行普通广搜即可。注意：因为有三个瓶子，故一共有6种移动状态：   1：从10L的瓶子向7L的瓶子中倒：  if(x10 > 0 && x7 < 7){ x10 = x10 + x7 - 7; x7 = 7; }  2:从7L的瓶子向3L的瓶子中倒：  if(x7 > 0 && x3 < 3){ if(x7 + x3 > 3){ x7 = x7 + x3 - 3; x3 = 3; ...

[题解]八数码问题 原题链 提交情况 解题思路： 广搜。首先读入，然后特判是不是不需要变换就直接是最后结果（有一个点）。接着入队当前状态，所需步数为。然后就是普通广搜的过程。分为个方向。每次进行扩展时，都现将表示当前状态的9位数变为一个的矩阵，然后扩展，并判断是否合法。如果合法，则又将的矩阵变为一个9位数作为函数的返回值。当一遍广搜进行完闭后，就判断是否为目标状态。如果不是，就进行判重。 源代码： #include <bits/stdc++.h> using namespace std; int end_state = 123804765; map < int,bool &g...

 对拍程序（linux）  使用说明：  这里使用compare.cpp程序来对拍的，没有用bash脚本 使用时，先编译4个文件(std中放正确的标程/暴力程序 my中自己的程序 rand是用来产生数据的) g++ compare.cpp -o duipai g++ my.cpp -o my g++ rand.cpp -o rand g++ std.cpp -o std​ 然后运行compare即可:./compare   compare.cpp #include <bits/stdc++.h> using namespace std; int main(){ for(int i ...

[题解]openjudge-回文素数 提交情况 原题链 解题思路 整体思路：首先生成一个满足为n位的回文数，再判断其是否为素数。 细节问题：我们枚举一个长度为长度的数，将这个数的前个数放到原数的后方生成新的回文数。example：我们需要一个长度为3为的回文数，那么我们要枚举的数是从~。假设我们枚举的一位数为10。那么最后生成的数即是101。 源代码 #include <bits/stdc++.h> using namespace std; int a[1000010]; const int mod = 7; inline int make(int tmp){ int ans = ...

[题解]编辑距离 原题链 提交情况 解题思路： DP。如果当前两个字符匹配，则步数不变，否则就进行判断：选出删除，插入或改变中的最小步数。 源代码 #include using namespace std; char s1[2550],s2[2550]; int f[2002][2002]; int n,m; int main() { gets(s1 + 1); gets(s2 + 1); int l1 = strlen(s1 + 1); int l2 = strlen(s2 + 1); for (int i = 1;i <= l2;i++) f[0][i] = i; for (int ...

#include <bits/stdc++.h> using namespace std; struct node{ int next,to,w; }e[1000010]; int first[1000010],a[1000010],ffffff,last = INT_MAX,len,dis[1000010],n; bool vis[1000010]; void add(int x,int y,int w){ e[++len].to = y; e[len].w = w; e[len].next = first[x]; first[x] = len; } void find(int)...