Deep_Dark_FAntasy♂

未归档

Codeforces(3) 博弈论(3) 基本数论、组合数学（排列组合，容斥等）(14) 并查集(2) 数据结构(2) 深度优先搜索、广度优先搜索、搜索剪枝(8) 线性dp、背包问题、区间dp(15) 题解(12)

/ 注册

全部文章 / 未归档（共7篇）

Zero Remainder Sum

#include<bits/stdc++.h> using namespace std; #define INF 0x3f3f3f3f int mp[75][75]; int dp[75][75][75][75]; //dp[i][j][k][r]定义为：当前行选了k个，和能够余r的最...

dp

2020-10-23

3 543

Camels and Bridge

链接：https://vjudge.net/contest/401586#problem/C题意：有n个骆驼过桥，骆驼的重量为w1,w2,...,wn，桥由M段连成，每段的长度为li,承重为wi,可以调整骆驼的先后顺序，问骆驼能通过桥首尾的最短距离为多少？思路：n很小，那么可以暴力出n的全排列。令d...

dp 二分

2020-10-22

4 566

数学考试

思路：fx表示1-x的排列对于前(pi<x)的限制都满足，但是不满足x的限制条件的个数。fx初始为n！现在要去掉不合法的，为了避免重复计算,应该减去所有pi的贡献，即fpi(n-pi)!。*代码：** #include<bits/stdc++.h> #define int long...

dp 组合数学

2020-10-10

3 494

Subsequence Count

链接：http://acm.hdu.edu.cn/showproblem.php?pid=6155思路：考虑构造dpdp[i][j]表示前i个，以j为结尾的不同子序列有多少个。如果第i个是1，那么dp[i][1]=dp[i-1][1]+dp[i-1][0]+1,dp[i][0]=dp[i-1][0]...

递推式线段树矩阵 dp

2020-09-30

3 511

单调栈+dp Discrete Centrifugal Jumps

题目链接：https://vjudge.net/contest/396106#problem/B思路：这题显然是个dp，dp的思路也很简单~，就是dp[i]为到i的最短跳跃数，我们来主要分析一下它的状态转移方程dp[i]能从三种情况转移过来，1.dp[i-1] 2.dpj13.dpj2？？那么显而易...

单调栈 dp

2020-09-22

2 660

A-Social Distancing(dp打表) 来自专栏

题目链接：https://ac.nowcoder.com/acm/contest/5672/A题目描述：求在一个半径r的圆内整点上放置n个人，使得两两距离和最大。(n<=8 r<=30)解题思路：考虑dp打表，状态dp[i][j][k]为放置i个点，横坐标和为j，纵坐标和为k的每个点和圆...

打表 dp

2020-08-03

1 594

K K-Bag 来自专栏

题目链接：https://ac.nowcoder.com/acm/contest/5671/K题目大意：一个由一些1-n的排列组成的数列称为k-bag。比如1，2，3，2，1，3，3，2，1就是一个k-bag。部分k-bag是k-bag的一个子串，现在给一个长度为n的数列，判断是否是一个部分k-ba...

尺取 dp

2020-07-29

1 523