G - 签到题 A - 简单题 题意就是给一堆区间把所有相交的区间合并，找出合并后，所有区间后的空隙有多少 void solve() { cin >> n; vector<pii> a; for (int i = 1, x, y; i <= n; i++) { cin >> x >> y; a.push_back({x - y, x + y}); } sort(ALL(a)); //ALL就是a.begin(), a.end() vector<pii> ans; for (int ...

接下来就是区间dp区间dp有个可以套模板，就是枚举区间长度，然后每个区间等于他的两个子区间相加最大/最小。。。直接上例题。最典型例题合并石子：http://120.78.128.11/Problem.jsp?pid=2385直接枚举每个区间长度一层一层往上就好了，类似于归并排序。需要注意的是这个是一个环形的所以直接复制一圈就好了 #include<bits/stdc++.h> using namespace std; int a[705],sum[707]={0}; int dp[705][705]; int dfs(int ,int ); int main() { int...

————dp非常灵活，对像我这样的蒟蒻及其不友好。写此小结记录下自己成长的过程首先呢，拿到一个题怎么发现他是由dp来解决的呢？有以下几点：1.可以由一个子问题推出一个全局最优解2.无后效性而做dp的题无非就三部曲1.确认子问题及其边界2.推出状态转移方程3.进行动态规划编程线性dp：线性dp过于灵活，不像区间dp以及背包问题那样有模板，就我目前你遇到的线性dp来做个总结首先呢就是LIS例题一：http://120.78.128.11/Problem.jsp?pid=1388给定一个序列求最长上升子序列。我觉得这是一个最最基础的dp题了。首先就是确认子状态了：假设dp[i]是序列第i个数的最长子...

题目描述：题目给你一个长度为n的序列，m次询问，每次询问给一个k，寻找有多少个区间【l，r】满足区间内的数组最大值减数组最大值大于k（不等于k）思路分析：我们给定一个i，为满足条件的区间左边界。然后往后找右区间边界，我们令j为区间右边界，而我们只需要找出这个区间内满足条件的最小j即可，因为这个j后面的右边界都满足条件。而我们可以用两个单调队列分别来维护这个区间内最小值和最大值。AC代码： #include<bits/stdc++.h> using namespace std; int m,n,k; long long ans; int mm,mx,mi,xi; int a[1000...

题目描述 :在网友的国度***有n种不同面额的货币，第i种货币的面额为a[i]，你可以假设每一种货币都有无穷多张。为了方便，我们把货币种数为n、面额数组为a[1..n]的货币系统记作(n,a)。在一个完善的货币系统中，每一个非负整数的金额x 都应该可以被表示出，即对每一个非负整数x，都存在n个非负整数t[i] 满足a[i] x t[i] 的和为x。然而，在网友的国度中，货币系统可能是不完善的，即可能存在金额x不能被该货币系统表示出。例如在货币系统n=3, a=[2,5,9]中，金额1,3就无法被表示出来。两个货币系统(n,a)和(m,b)是等价的，当且仅当对于任意非负整数x，它要么均可以被两个...

题目描述：设有NxN的方格图(N ≤ 10,我们将其中的某些方格中填入正整数,而其他的方格中则放入数字0。如下图所示(见样例)：某人从图的左上角的A 点出发，可以向下行走，也可以向右走，直到到达右下角的B点。在走过的路上，他可以取走方格中的数(取走后的方格中将变为数字0)。此人从A点到B 点共走两次，试找出2条这样的路径，使得取得的数之和为最大。思路：作为一个dp新手来说，用递推的方式来解这题还是由点难以想到的，于是我就尝试用记忆化搜索来做发现也可以。1.首先就是用一个四维数组来保存每次计算出的值四维的前两维用来保存第一人的位置，后两维保存第二位的。2.用dfs遍历两个人每次分别位置取得的最大...

题目描述：给你一个数组a，a[i]可以加1或者不加，求进行所有操作完后最小的逆序对数思路：先把所有的逆序对数求出来，然后再找满足(a[i]>a[j]&&i<j&&a[i]==a[j]+1)条件的对数，再用所有的逆序对数减去满足条件对数就可以的出最小对数。AC代码 #include<bits/stdc++.h> using namespace std; int num[200005]; int b[200005],ans[200005]; long long sum=0; void gbsort(int l,int r,int a[]) {...

题目描述：求一个数组求逆序对的数量。方法与解析：直接套归并排序的板子，归并板子来自牛客笔记 #include<bits/stdc++.h> using namespace std; const int N=1e5+10; void b_sort(int l,int r); void bing(int ar1[],int len1,int ar2[],int len2,int ar[],int mid); int a[N],b[N],n; long long ans=0; int main() { cin>>n; for(int i=1;i<=n;i...

题目描述： 简单来说就是给你两个数组，a和数组b。然后定义矩阵w[i][j]=a[i]+b[i]，在这个矩阵内找一个子矩阵得到，这个字矩阵内的平均值最大，这个子矩阵长不得小于x,宽不得小于y。题目分析： 每个矩阵的平均值为:又由于w[i][j]=a[i]+b[j]得子矩阵的和就等于平均值就为这样就可以吧题目分为分别找第一项的最大值与第二项的最大值的和，由于题目给的大小为1e5我们可以用二分来找最大值。 bool check(ll x,ll*v,int tx,int t) { for(int i=1;i<=t;i++){ ans[i]=v[i]+ans[...

题目描述:给定两个长度为n的整数列A和B，每次你可以从A数列的左端或右端取走一个数。假设第i次取走的数为ax，则第i次取走的数的价值vi=bi⋅ax，现在希望你求出∑vi的最大值。思路与分析：我们定义它在区间[l,r]之间的最大值为dp[l][r]。而dp[l][r]的值是由max(dfs(l+1,r,i+1)+b[i]a[l],dfs(l,r-1,i+1)+b[i]a[r])得来的。所以我们可以的到dfs的代码 int dfs(int l,int r,int i) { if(i==n+1)return 0; if(dp[l][r]!=0)return dp[l][r]; ...

题目描述： 小Q刷题计划在m天刷n题，每题有个难度值，定义难度为每天刷的题最大难度值与最小难度值差的平方，整个计划的 难度为每一天难度的总和。小Q可以按照任意顺序刷题，一天可以刷多道，每题只做一次，求总难度最小值。 分析与思路： 首先将所有的题目从大到小排序，以方便我们在后面算出难度值差。 由题目定义每一天难度值为d[i]枚举每一天以及当这一天做到第k道题时的最小 。要得到最小就要枚举每天做的题的最小难度值。 由此可得状态转移方程为dp[i][k]=min(dp[i][k],dp[i-1][j-1]+(a[k]-a[j])*(a[k]-a[j])); AC代码如下： #include<b...

题目描述： Taotao的电脑带不动绝地求生，所以taotao只能去玩pc版的荒野行动了，和绝地求生一样，游戏人物本身可携带一定重量m的物品，装备背包之后可以多携带h（h为0代表没有装备背包）重量的东西。玩了几天taotao发现了一个BUG，当装备背包之后，如果可携带重量没有满，就可以拿一个任意重的东西。（解释看样例）有一天taotao空降到了一个奇怪的岛上，岛上有n件装备，每个装备都有重量Wi和威力值Vi,但taotao不认识这些装备，所以他来求助你，挑选威力最大的装备，帮助他吃鸡。思路：首先他是一个背包问题，我们就可以在外层枚举第i个物品，进行取或者不取的情况讨论并取得最优解。则可推...