传送门 我们yy一下，一个数不可能被移动超过222次，否则就不是最优解，我们可以这么想，移动之后的序列一定是有序的，也就是说它是固定的，问题就转化为钦定几个单调递增的数的位置，它们不移动，移动其它的数，使序列变得有序。 既然要让移动的数的总和尽量小，那就要让没有移动的数的总和尽量大，问题就转化为求序列的和最大的上升子序列，dpdpdpO(n2)O(n^2)O(n2)求一下即可。 123456...

传送门 建议先做这道题，有一些套路是一模一样的。 考虑如何dpdpdp，dp[i][j]dp[i][j]dp[i][j]表示现在扫到第iii个数，用了jjj段区间，最大的总价值，cnt(l,r)cnt(l,r)cnt(l,r)表示在区间[l,r][l,r][l,r]中不同的数的个数。 考虑在区间[1,p][1,p][1,p]分段，很容易列出dpdpdp方程： dp[i][j]=max⁡{dp...

考虑dp\rm dpdp，其中f1[i][j]f1[i][j]f1[i][j]表示由起点到达iii，走的是路径111，路径总长度为jjj的方法可不可行，f2f2f2类似，拓扑排序的过程中大力转移即可。 转移过程类似背包问题。 好像可以用bitset\rm bitsetbitset优化，少一些常数。 注意输出IMPOSSIBLE!\rm IMPOSSIBLE!IMPOSSIBLE! 1234...

传送门 考虑dpdpdp，但是这个dpdpdp该怎么ddd呢？ 如果走路的时候能往右就往右，实在不行（有障碍物或往上走会产生新的方法）才向上 （也就是尽可能向低处走），我们就可以做到路径不“重复”。 于是dpdpdp就呼之欲出： F[i][j]=F[i−1][j]F[i][j]=F[i-1][j]F[i][j]=F[i−1][j] 一般情况 F[i][j]=0F[i][j]=0F[i][j]...

传送门 注意：XkX_kXk​为位置，而kkk才是真正加进去的数。 加入的序列为1,2,3,......1,2,3,......1,2,3,...... 也就是说，每次加入的数都是当前最大的。 那么我们很快就可以推出dpdpdp方程： dp[i]=max(dp[i],dp[j]+1)j<idp[i]=max(dp[i],dp[j]+1) j<idp[i]=max(dp[i],dp...

设iii个点的连通块个数为F(i)F(i)F(i)，所有iii个点的图的个数为G(i)G(i)G(i) 从反面考虑问题，发现iii个点连通图个数=所有iii个点的图的个数-iii个点非连通图的个数。 考虑所有iii个点的图的个数，每条边可选可不选，共i×(i−1)/2i \times (i-1)/2i×(i−1)/2条边，则G(i)=2i×(i−1)/2G(i)=2^{i \times (i...