区间dp用dp[i][j]表示区间i~j的最小涂色次数如果i和j的颜色一样，就可以转化为dp[i][j-1]或者dp[i+1][j]如果不一样，就枚举i和j中间的每一个，计算dp[i][k]+dp[k+1][j]的值 #include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #include <string> #include <stack> #include <queue> #include <cmath&...

和之前的着色方案差不多用dp[a][b][c][d] ，a表示1的卡片，b表示2的卡片，c表示3的卡片，d表示4的卡片然后直接搜索就行了 #include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #include <string> #include <stack> #include <queue> #include <cmath> #define ll long long #define pi 3.14...

维护一个单调递增的队列，如果一个新的柱比之前的短，那就更新最大的矩形方案。 #include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #include <string> #include <stack> #include <queue> #include <cmath> #define ll long long #define pi 3.1415927 #define inf 0x3f3f3f3f #d...

要把一个带负边权的图改为非负的，并且还要最短路的路径不变可以利用spfa的缩放 因为dis[v] > dis[u]+w 所以dis[u]-dis[v]+w > 0用一个节点作为超级源节点，与每一个的距离都是0，然后spfa进行缩放 #include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #include <string> #include <stack> #include <queue> #incl...

把式子拆分之后可以发现，它是在区间长度为1-n的范围内求各种前缀和，可以用一些例子分析一下怎么计算如果n为6（对号代表要加上这些a[i]）可以发现，随着范围增加，会多出一部分的值，可以用 sum[n-i+1]-sum[i-1]来算这些多出的值（sum[i]代表前缀和）再继续往后的时候，会倒过来，4和3一样，5和2一样，6和1一样 #include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #include <string> #include...

对于每种油漆，如果它能涂的数量相同，那对结果贡献就是相同的，所以，用dp[a][b][c][d][e][las],a,b,c,d,e表示还能涂1,2,3,4,5个木块，las表示上一次涂的是哪一种剩余量的油漆。 假如上一次涂的是剩余量为2的油漆如果当前 a 还有剩余，那么最终结果应该加上: ( a - 1 )dp[a-1][b][c][d][e][1](因为上一次涂的是剩余量为2的油漆（b），涂完之后，剩余量为1的油漆就会多一个，因此这里是 a - 1 )如果b还有剩余 那么应该加上： bdp[a+1][b-1][c][d][e][2](b还有剩余，就涂一个b，然后a就多了一个) #incl...

因为碗的数量很少，直接全排列求所有叠放情况就行了，然后考虑两个碗之间的关系。一共有四种情况1，如果上面的碗的底比下面的碗口大，那就直接堆上去2，如果上面的碗的碗口小于了下面的碗的底，那就放到下面的碗里面了3，上面的碗斜率小于下面的碗，再看有没有放到碗底4，下面的碗斜率小于上面的碗，看碗有没有完全放进去 #include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #include <string> #include <stack>...

每次询问一个点，会让当前节点和父亲节点和儿子节点+1，而父亲节点和儿子节点受到影响之后，也会让祖父节点和孙子节点受到影响，所以我们用三个数组受到影响的次数来进行计算。定义a,b,c分别表示当前节点+1的次数，儿子节点+1的次数，孙子节点+1的次数。而父亲节点和祖父节点我们可以用fa[]来表示。每次询问之后，当前节点造成的影响就是：a[i]+b[i]+a[fa[i]] 自己节点的次数+儿子节点的次数+父亲节点的次数对于父亲节点，造成的影响是：a[fa[i]]+b[fa[i]]+a[fa[fa[i]]] 父亲节点的次数+父亲的儿子节点的次数+祖父节点的次数而儿子节点的贡献是：b[i]+c[i]...

每次切蛋糕只有两种情况，横着切和竖着切，并且最大只有10个人，所以直接dfs。如果切x，那么只能在x均分成n份的地方切，也就是x/n的倍数，模拟每种情况即可。 #include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #include <string> #include <stack> #include <queue> #include <cmath> #define ll long long #def...

如果没有M的话，是一个正常的区间dp，我们可以列出来它的转移方程① dp[l][r]=min( dp[l][r] , dp[l][j] + dp[j+1][r] );如果当前区间（l，r）前半段和后半段相同，那就将它压缩一半然后加上一个R：② dp[l][r]=min( dp[l][r] , dp[l][j] + 1 ); 但是现在有一个M，因此就再加一种情况，定义dp[l][r][0/1],表示区间(l，r)有M和没有M时的最小值。没有M时，我们要改一下①的式子，变成：① dp[l][r][0]=min( dp[l][j][0] + r-j , dp[l][r][0]); （l<= j...

题意看了好久才明白什么意思(:з」∠)一开始以为只有最底部的节点需要传递信息，但其实是每个官员都要传递信息。 比如这个图，红色是国王，蓝色的三个是非重儿子的节点（还有其他节点没画），传递信息的时候，蓝1传给国王花费1，蓝2是蓝1的重儿子，传给蓝1不花费，蓝1再传给国王再花费1，蓝3传给蓝1花费1，再传给国王又花费1。所以这颗蓝色的树一共花费了4. 我们用一个ans[n]来记录n个节点的最大花费，dp[i][j]记录i个节点中，最大子树不大于j个节点的最大花费。如果重儿子的节点为j，那么ans[n]可以由dp[n-j-1][j]+n-j-1+ans[j]得到，所以ans的转移方程就是ans[n...

思路： 因为是在每行的首尾取数，所以每行都互不相关，因此分别对每行进行处理就行了。 每次取首尾一个数，就可以转化为在区间（l，r）中取max( dp[l][r-1]+a[r],dp[l+1][r]+a[l])。注：数据会爆long long ，可以用int128 #include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #include <string> #include <stack> #include <queue&...

题意： 给一个二分图染色，有公共点的边不能同色，求最小的颜色方案。 思路： 因为有公共点的边不能染同种颜色，所以，连的边最多的点就是要染的颜色数量了。 方案的求法，可以先从度最大的点开始，求出最大匹配，然后染色，之后再找下一个度最大的求最大匹配，染色。 #include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #include <string> #include <stack> #include <queue> #...

思路： 因为边的数量最多比点多100个，所以先把多余的那些边去掉，用lca计算最短路，然后再把多余的边加上，再对这些多余的边进行bfs。去掉和加上多余边的方法：在存图的时候，利用并查集判断一下，如果这两个点有同一个父亲节点，那就证明这个边是多余的，就先把它给存起来而不加到图里。 #include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #include <string> #include <stack> #include &l...