和P3628 [APIO2010]特别行动队 差不多，都是序列拆成几个连续子段，每段都有一个权值，求权值最大/最小。 于是如法炮制。 dp[i]:dp[i]:dp[i]:前iii个的总代价最小值。 众所周知，后面的权值会被前面的决策影响。 所以每次更新的时候加上如果这样决策后面的数增加的权值。 于是枚举上一个断点。 设t[i]t[i]t[i]前缀和为a[i]a[i]a[i]，c[i]c[i]c[i]后缀和为b[i]b[i]b[i]。 dp[i]=j=0i−1dp[j]+b[j+1]∗(s+a[i]−a[j])dp[i]=\min_{j=0}^{i-1} dp[j]+b[j+1]*(s+a[i]...

观察到ttt很小，于是考虑在时间轴上dpdpdp。 设c[i]c[i]c[i]为在iii时刻出发的人数。 设dp[i]dp[i]dp[i]是在iii时刻出发，前iii分钟等待时间最少的值。 所以 dp[i]=j=1i−mdp[j]+∑k=j+1i(i−k)∗c[k]dp[i]= \min_{j=1}^{i-m} dp[j]+ \sum_{k=j+1}^{i}(i-k)*c[k]dp[i]=minj=1i−m​dp[j]+∑k=j+1i​(i−k)∗c[k] 单独看后面那一坨东西： ∑k=j+1i(i−k)∗c[k]\sum_{k=j+1}^{i}(i-k)*c[k]∑k=j+1i​(i−k)∗...

能填的数≤200\leq 200≤200。 hmmmmmm。。。。 于是dp[i][j][k]dp[i][j][k]dp[i][j][k]表示填到iii，这一位填jjj，前一位填kkk。 然后是O(n∗2002)O(n*200^2)O(n∗2002)的啥都别说了就是不可能过得去算法。 然后我们发现这一位填的数和上一位填的数的绝对大小不重要，只需要知道相对大小。 于是dp[i][j][k]dp[i][j][k]dp[i][j][k]表示填到iii，这一位填jjj，前一位填大于/等于/小于jjj。 于是推个式子，再搞个前缀和就做完了。

考虑链上的联通块性质。 发现对于f(l,r)f(l,r)f(l,r)中，设一个联通块[x,y][x,y][x,y]（位置），那么它一定满足ax−1∉[l,r],ay+1∉[l,r],ax∈[l,r],ay∈[l,r]a_{x-1}∉[l,r],a_{y+1}∉[l,r],a_x∈[l,r],a_y∈[l,r]ax−1​∈/​[l,r],ay+1​∈/​[l,r],ax​∈[l,r],ay​∈[l,r]。 于是我们只用数这个序列中有多少个相邻的位置使他们一个在区间里，一个不在，然后除以222，就是联通块个数。 于是它O(n3)O(n^3)O(n3)啦！ 于是它<mtext>TLE&n...

首先方差的式子： S2=1m∑i=1m(x‾−xi)2S^2=\dfrac{1}{m}\sum_{i=1}^{m}(\overline{x}-x_i)^2S2=m1​∑i=1m​(x−xi​)2 =1m∑i=1mx‾2−2x‾xi+xi2=\dfrac{1}{m}\sum_{i=1}^{m}\overline{x}^2-2\overline{x}x_i+x_i^2=m1​∑i=1m​x2−2xxi​+xi2​ =1m∑i=1m(summ)2−2(summ)xi+xi2=\dfrac{1}{m}\sum_{i=1}^{m}(\dfrac{sum}{m})^2-2(\dfrac{sum}{m})x...

参考https://ac.nowcoder.com/acm/problem/16739 均分纸牌 均分纸牌这道题是移动纸牌，就相当于相邻的两堆一堆+1，一堆-1，就是此题了。 代码： #include<bits/stdc++.h> using namespace std; #define ll long long #define f(i,a,b) for(int i=a;i<=b;i++) inline ll r() { ll x=0,f=1; char c=getchar(); while(!isdigit(c)){if(c=='-')f=-1;c=...

果不其然，又是字符串操作题。 首先，我们很容易想到用struct来存每个妹子的信息。 那么根据题意，我们就需要定义这样一个结构体： struct node{ string nm;//妹子的名字 ll rk;//妹子的评分 int x;//输入顺序 };题目中问法有些有趣：询问名字以某个字母结尾的妹子。 所以我们就可以定义一个数组，表示结尾字符为，排名第的妹子。 所以再加上排序函数，整个程序就写好了。 不过，有一个问题：内存超了。 那怎么办？我们有万能的！ 再加上这玩意有自带的排序函数，然后就写完了。 #include<bits/stdc++.h> using...

让我们想一想，n划分成什么最优？ （首先一定要保证划分出来的数接近） 来暴搜枚举一下： n=1:1=1 n=2:2=2 n=3:3=3 n=4:4=2*2 n=5:6=2*3 n=6:9=3*3 n=7:12=3*2*2 n=8:18=3*3*2 n=9:27=3*3*3 ...... 都是2或3呢~ 所以得到贪心数学策略：取3取到n<3或n=4 进一步： if(n%3==0)ans=pow(3,n/3); if(n%3==1)ans=pow(3,n/3-1)*4 if(n%3==2)ans=pow(3,n/3)*2所以有了30分代码： #include<bits/stdc++.h...

题解三角形 这题……真的是省选吗？ 首先，有一个很重要的性质！！！ 观察这幅图（题目里的）： 每个三角形最多与个三角形相邻！！！ 理论解释： 首先我们知道， 如果B不包含A，且A的某一条完整的边是B的某条边的一部分，则我们说A靠在B的边上 ---P4536 [CQOI2007]三角形 解读这句话：的某一条完整的边是B的某条边的一部分 对于三角形： 有三条边（废话） 每条边都（可能）有一个三角形与相邻，根据定义，B的边长≥A的边长。所以A的这条边上不可能再有别的与相邻的三角形（重要！！） 那么就是说每条边上最多只有1个三角形与它相邻 那么最多只有个三角形与它相邻啊！！！ 这样一...

口胡五分钟，代码两小时！ 这个题啊，真是好写，也不好写。 好写呢，在于建个图，再跑一遍，比较最小值，就没了 不好写呢，就在于： 1.每个矩形只给了3个点..... 2.代码长（可能不是），相近的变量多（这是我）等等 来一步一步分析吧。。。 题意: （略） 建图 找到矩形的另外个点 这个东西咋找呢？用亿点初中几何知识知道矩形是平行四边形，而平行四边形是对角线互相平分的。 如图所示： 其中，点为输入的点，是所求的点，对角线交点为 这个例子中，是一条对角线，是另一条。根据中点公式，可以得到 所以可得 于是， 我们再用勾股定理判断一下哪两个点构成对角线，然后就能求出这个点啦！ 建图 这里我们...