- 博客(18)
- 收藏
- 关注
RSS订阅原创 ACwing 143. 最大异或对
题目描述：解答： 因为这里只需要两个数字的异或对最大，所以我们可以考虑将数字拆分成2进制， 将数字的每一位都存储下来，然后再逐个进行比对，我们可以联想到用字典树。下面附上代码：#include <bits/stdc++.h>using namespace std;typedef long long ll;const int maxn = 1000010;...
2020-01-16 18:01:27
190
原创 力扣 343. 整数拆分
题目描述：解答：这个题看完题意之后，大致可以猜到是类似dp的题，dp[i]表示数字i的最大乘积，dp[i] = max(dp[i],dp[j]*dp[i-j])，然后暴力即可，对于这种题，好像有公式。下面附上代码：class Solution {public: int dp[60]; void init(){ dp[1] = 1; dp...
2020-01-16 17:46:33
192
原创 51nod 1391 01串
题目描述：解答：第一眼看到这个题目，只想到了将0转为-1（貌似曾经见过一次这种类型、印象比较深），然后想前缀和，但是对于X的这个位置，想了很久，看了眼复杂度，应该是 O (n) 的方法。正文：维护一个leftlen[i] ： 以i为结尾，0比1多的长度。 rightlen[i]：同理；pos[n] ： 数n第一次出现的位置。遍历数组，if(sum[i]<0) leftlen[i]...
2020-01-10 15:55:55
99
原创 51nod 1084 矩阵取数问题 V2
题目：一个M*N矩阵中有不同的正整数，经过这个格子，就能获得相应价值的奖励，先从左上走到右下，再从右下走到左上。第1遍时只能向下和向右走，第2遍时只能向上和向左走。两次如果经过同一个格子，则该格子的奖励只计算一次，求能够获得的最大价值。例如：3 * 3的方格。1 3 32 1 32 2 1能够获得的最大价值为：17。1 -> 3 -> 3 -> 3 -&g...
2019-09-17 20:31:22
109
原创 51nod 1055最长等差数列
我太菜了，没想到这个题怎么做给出大神的链接链接：https://blog.csdn.net/liuyanfeier/article/details/50760657思路：dp[i][j]表示以i,j为开头的等差数列，从后向前扫描 当a[i]+a[k]==2*a[j]时，dp[i][j] = dp[j][k]+1。#include<iostream>#inclu...
2019-09-17 19:05:48
93
原创 2019.4.8 hdu 3549 Flow Problem
题意：网络流最大流直接上代码#include <bits/stdc++.h>using namespace std;#define inf 0x3f3f3f3fint head[1050],tot = 0;struct Node{ int to,next,w;}edge[2000000];void add(int x,int y,int z){ ...
2019-04-09 00:11:54
66
原创 2019.4.8 1532 Drainage Ditches
题意：水从水池流向汇集地，每个管子有限制，求到汇集地的最大量最大流模板#include <bits/stdc++.h>using namespace std;#define inf 0x3f3f3f3fint head[210],tot = 0;struct Node{ int to,next,w;}edge[200000];int s,t;vo...
2019-04-09 00:10:13
93
转载 2019.4.4 51nod 1043 幸运号码
转载：http://www.cnblogs.com/geloutingyu/p/6329594.html第一眼看过去，没有什么思路，然后也没想到用数位dp怎么写，看了很久大神的代码，才想明白人家是怎么想的#include <bits/stdc++.h>#define ll long longusing namespace std;const int mod=1e9+...
2019-04-05 23:22:07
94
原创 2019.4.4 51nod 1086 背包问题 V2
题意：多重背包裸题，直接模板。#include<bits/stdc++.h>using namespace std;int dp[50005];int cc[105],vv[105],mm[105];int n,W;void b0(int c,int v){ for(int i = W;i>=c;i--){ dp[i] = ma...
2019-04-05 23:18:23
111
原创 2091.4.3 51nod 1021 石子归并
题意：给出n个数字，求出最小组合和，1 2 3 4 => 3 3 4(3) => 6 4(9) => 10(19) 1 2 3 4 => 1 5 4(5) => 1 9(14) => 10(24) 1 2 3 4 => 1 2 7(7) => 3 7(10) => 10(20)。区间dp，dp[i][j]表示 从i到j最小...
2019-04-03 23:57:36
78
原创 2019.4.3 51Nod 1051 最大子矩阵和
题意：给出一个m*n的矩阵，求出和最大的子矩阵，如果为负数，那么就输出0最大子段和是一维数组，而这个要求是最大子矩阵，换汤不换药，我们只需要看每一列，我们先做一个前缀和，然后对于（i-j）行的子矩阵，把每一列的值逐次相加（和求最大字段和的思想相同，只要这个sum[i-1]不为负，那么加上一定使和增大了）。#include<bits/stdc++.h>using nam...
2019-04-03 23:43:20
68
转载 2019.4.3 51Nod 1270 数组的最大代价
转载：https://blog.csdn.net/dannis_bh/article/details/52649922dp[i][0]::=前i项构成的子问题中，当Ai=1时的最大代价dp[i][1]::=前i项构成的子问题中，当Ai=Bi时的最大代价我们可以想象，能够得到最大代价的序列肯定是需要每一步都取极端值的，这样才能尽可能让波动最大化。递推关系：dp[1][0] = dp[1]...
2019-04-03 16:30:15
69
原创 2019.4.2 51Nod 正整数分组
题意：把n个数字分两组，求最小差值。01背包，求出dp[ave]，这就是第一组最接近ave的和，然后用sum-2*dp[ave]即可。（记得abs 不能出现负数）#include<bits/stdc++.h>using namespace std;int dp[100005];int a[100005];int sum = 0;int main(){...
2019-04-03 13:00:45
109
原创 2019.4.2 hdu 1078 FatMouse and Cheese
题意：给出一个n*n矩阵，每个数字a[i][j]代表i行j列处的奶酪大小，一个老鼠可以移动k步，但是新的位置必须满足a[i][j+k]>a[i][j]（四个方向都可以移动）对于每个位置，求出在当前位置可以获得的最大量奶酪，往回回溯，直到dp[0][0]位置，即为所求。（需要用到记忆化）。#include<bits/stdc++.h>using namespace...
2019-04-03 12:55:54
82
原创 2019.4.1 hdu 1059 Dividing
题意：六种石头，每个石头的价值按1,2,3,4,5,6排序，给出每块石头的个数，问是否可以取出(总价值/2) 。典型的多重背包，此题替换为：sum/2的总体积可以放入最大价值是多少。#include<bits/stdc++.h>using namespace std;int dp[100005];int a[10];int sum,ave;void b0(i...
2019-04-01 23:49:58
74
原创 2019.4.1 hdu 1058 Humble Numbers
题意：一个数字只有当它的因数为2,3,5,7（其中的一个或多个）时 那么它就是简单数，求第n个简单数。借鉴了 大神的代码（很简洁）。简单的说，最笨的方法就是从1到无穷大的遍历，而我们需要更简单的方法就是用最小的数生成第二小的再生成第三小的。。以此类推下去，每次生成之后找到哪个是最小的 然后更新 继续生成下一个。#include<bits/stdc++.h>usi...
2019-04-01 23:44:52
78
原创 2019.4.1 hdu 1028 Ignatius and the Princess III
题意：一个数 可以分解成多个数相加，有多少种方案。对于每一个数字n，可以把他分成1,2,3,4....n,组然后最后把所有方案数加在一起，就是n的总共能分的方案数。对于每一种情况：可以考虑成有n个1，a.在结尾处去掉1。b.数字i减去j个1，剩下的1分成j组有几种方案； dp[i][j] = dp[i-j][j]+dp[i-1...
2019-04-01 23:37:03
133
原创 2019.4.1 hdu 1051 Wooden Sticks(贪心）
题意：当l<=l'和w<=w'时，那么不需要花费时间，否则需要花费1分钟，求最短时间。第一个想法就是先按l非递减顺序（一定要记得判断==的情况，因为这个WA一发）排序（按w也可以），然后开一个vis数组判断该值是不是被取过（此处无需担心该值是不是不应该在此队列里，因为每一个值都会被选入一个队列中，等效了），实时更新minn,minm的值。#include<bi...
2019-04-01 22:14:54
52
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人