https://www.luogu.org/problemnew/show/P1387 开始自己想的：设f(i,j):以（i，j）为左上角的包含（i，j）的最大子正方形大小，则f(i,j)取决于：设t=f(i+1,j+1)，（i，j）右以及下方的t个元素最多连续几个1。由于只有01，所以用前缀和+二分可以o（logn）知道有几个连续的1，二分很麻烦写，不写的话用了前缀和也没什么用。 #include<bits/stdc++.h> using namespace std; int n,m,maxn; int a[105][105],d[105][105]; int row[1...

每个骨牌上下相差最多为6-1=5，1000个骨牌最多相差5000，考虑正负，偏移5000，可以开10000大小的数组存上下差值 设f(i,j)：前i个骨牌，上比下多j-5000个对应的最少旋转次数。 f(0,5000)=0,f(0,j)=inf f(i,j)=min{f(i-1,j-(a[i]-b[i])),f(i-1,j-(b[i]-a[i]))+1} 最后看前n个骨牌在5000附近最近的可行的差值对应的旋转次数。 #include<bits/stdc++.h> using namespace std; int n,a[1005],b[1005]; int f[10...

设f(i,j)表示第i堆到第j堆合并的总最大得分，f(i,j)=max{f(i,k)+f(k+1,j)+sum[i~j]} 由于是环形的，n的环写成2*n的链，环的最优值等于n条以不同点为起点的链的最优值之中最优的那一个。 如123456->123456123456，然后dp就可以轻易做分别以123456开头的6条链的最优值了。 #include<bits/stdc++.h> using namespace std; int n,a[205],d[205][205],d2[205][205]; int sum[205]; int main() { freopen...

https://www.luogu.org/problemnew/show/P1140 根据题目给出的碱基配对表，发现： 1.两基因相同时产生+5，其余都是负数。 2.任意两个不同基因相配，直接配要好于分别与空碱基配。但是两基因不满足上1点的长度不同，所以必须有一些基因与空碱基相配。 设f(i,j)表示第一个基因前i个和第二个基因前j个相配的最大相似度 边界为f(0,j)=第二个基因前j个分别与空基因相配的相似度      f(i,0)=第一个基因前i个分别与空基因相配的相似度 f(i,j)=      f(i-1,j-1)+5    ,a[i]==b[j]          ...

https://www.luogu.org/problemnew/show/P1280 设d(i)为尼克从第i分钟开始着手工作一直到结束所花费的最少工作时间。 d(i)=    d(i+1),i时无任务            d(i+t)+t,i时有一个任务            min{d(i+t)+t},i时有多个任务   注意边界是n+1时为0，因为n时可能会有时长为1的任务。 #include<bits/stdc++.h> using namespace std; int n,k,d[10005]; vector<int> mission[10...

1.

https://www.luogu.org/problemnew/show/P1020 第一问就是最长不上升子序列，第二问题解说用离散数学里的Dilworth定理，看不懂证明，它的结论是：将序列划分若干个为不上升子序列，使得划分的个数最小，那么这个个数等于序列的最长上升子序列的大小。 #include<bits/stdc++.h> using namespace std; int n; int d[100005]; int L=1,R=0; int d2[100005]; int binary(int v) { int l=L,r=R,m; while...

https://www.luogu.org/problemnew/show/P1616 完全背包，可以用一个常数优化，对于同一个价值的量，仅保存花费最小的那个就行了，因为每种都有无限多个。 #include<bits/stdc++.h> using namespace std; int n,V; int c[10005],w[10005]; int d[100005]; int MinCost[10005],pos; void CompletePack() { for(int i=1;i<=n;i++) for(int j=c[i];j<=V;j++...

https://www.luogu.org/problemnew/show/P1064 分组背包，由于每组里的情况很少，只有5种，所以就不需要每组内部01背包过一遍了。只需要把主件附件放到一组里，像01背包那样，只是在每组里考虑所有的组合。考虑组合时也是需要考虑一下怎么写可以简化代码的。 #include<bits/stdc++.h> using namespace std; int V,n; vector<int> c[65],w[65]; int d[32005]; void ZeroOnePack() { for(int i=1;i<=n;i++...

从自己的直观感觉上，应该目标函数是一个单峰函数，因此不需要用到模拟退火的思想----以一定的概率接受更差解，只需爬山即可。这玩意儿太玄学了，大概是刚学，还不太理解这个过程吧。自己写的爬山一会儿在bzoj可以过，洛谷过不了，修改了一些参数后又恰恰相反，而且还有精度低时洛谷可以过，把精度调高反而wa了，很是玄乎。 写法一： #include<bits/stdc++.h> using namespace std; int dx[]={1,0,-1,0},dy[]={0,1,0,-1}; int n,x[10005],y[10005],w[10005]; double T=2000...

高中学的是vector<int>实现的高精度，很不好写。今天学习了字符串数组实现的高精度，直接用数组下标作为位移量，感觉比较自然。就拿它作为今后的模板了。该模板主要来自于大佬https://blog.csdn.net/u013615904/article/details/43373601，自己在某些细节处作了一些改动，以符合自己的习惯。 //高精+高精 #include<iostream> #include<cstring> #include<algorithm> using namespace std; const int L=110;...

P1803 凌乱的yyy / 线段覆盖 对于每个开始时间，只能选择参加一次比赛或者不参加比赛，因此只考虑对于一个开始时间结束最早的比赛。设d（i）为i时间及其之后开始的最多参加的比赛数，则若i时间没有开始的比赛，d（i）=d（i+1），否则d（i）=max（d（i+1），d（i开始的结束时间）+1）。 #include<iostream> #include<cstring> using namespace std; int n,a[1000005],d[1000005]; int main() { memset(a,-1,sizeof(a)); ...

https://www.luogu.org/problemnew/show/P1309 看到题目，先想到每局sort一次，简单但一定会超时。然后想到，在一个2*n的有序数组里，每次只有n个元素+1，一定有高效的方法。想到如果用链表或者数组模拟链表，对于每局比赛，输的不管，赢得还保持原来的相对顺序，故在链表从前往后扫一遍，依次把递增的元素排到正确的位置，这样可以实现每局比赛o（n），但是非常难写。 看题解，用到了归并排序的思想。假设每局比赛之前数组已经排好序，那么对于这局比赛赢的人来说，他们重排后在数组中的相对位置不变，对输的人也是，故开一个辅助数组，分别记录本局输和赢的人的相对顺序，然后依...

洛谷p1177模板题https://www.luogu.org/problemnew/show/P1177 题目数据两组乱序的检验算法正确性，一组重复元素，一组正序，一组倒序+重复。 快排算法在递归树中，每层时间近似o（n），算法效率主要取决于每个节点的划分情况，这决定了树中一共有多少层，最好logn层，最差n层。 算导最开始的朴素算法在处理大量重复和大量有序时都表现不好，达到最差o（n^2），随机化原始序列或者随即化主元后，可以处理有序序列，但无法处理重复序列。用朴素的两路三路快排可以处理重复，用o（nlogn）无法处理有序序列，随机化后就卡不掉了。 随机打乱数组元素顺序函数：ran...