P8548小挖的买花（双重限制之限制一个最大一个最小）题目传送门：小挖的买花题解题目分析这道题目是一个多重限制的01背包变种，而且一个限制是限制最大，另一个是限制最小三维状态表示方式：dp[i][j][k],表示前i朵花，费用最大为j，新鲜度最少为k的状态中美丽度最大的状态状态转移：转移方式不选第i枝花直接由dp[i-1][j][k]转移来选第i枝花(判断是否满足限制金额大于等于第i枝花的金额)1.当前的花(第i枝花)直接能满足k需求(即第i枝花的新鲜度大于k)2.第i枝花新鲜度不够k，从之前减去第i枝花金额的j和减去第i枝花新鲜度的k的状态转移过来dp[i][j][k]=dp[i-1][j]
Atcoder链接：CoinsLuogu链接：Coins$\scr{\color{BlueViolet}{Solution}}$观察数据，发现$\cal{n}\le3000$，说明$Ο(\cal{n^2})$可过,容易想到DP。用$\cal{dp[i][j]}$表示抛完第$\cal{i}$个硬币时，有$\cal{j}$个硬币正面朝上的概率。 考虑$\cal{dp[i][j]}$如何转移，易发现有以下两种情况，（当前正面朝上概率为$\cal{p_i}$）：本次抛得硬币是正面：抛到正面概率乘抛完第$\cal{i-1}$个硬币后，有$j-1$个硬币朝上的概率。本次抛得硬币是反面：抛到反面概率乘抛完第
Atcoder链接：CoinsLuogu链接：Coins$\scr{\color{BlueViolet}{Solution}}$观察数据，发现$\cal{n}\le3000$，说明$Ο(\cal{n^2})$可过,容易想到DP。用$\cal{dp[i][j]}$表示抛完第$\cal{i}$个硬币时，有$\cal{j}$个硬币正面朝上的概率。 考虑$\cal{dp[i][j]}$如何转移，易发现有以下两种情况，（当前正面朝上概率为$\cal{p_i}$）：本次抛得硬币是正面：抛到正面概率乘抛完第$\cal{i-1}$个硬币后，有$j-1$个硬币朝上的概率。本次抛得硬币是反面：抛到反面概率乘抛完第
前言今日偶然打开\(oi-wiki\)，发现树形\(DP\)例题正好是之前在洛谷上鸽着的一道题。所以......\(\color{red}{很高兴以这样的方式认识你，树形DP!}\)这例题造的太好了，简直是无痛入门（感动.jpg）P1352没有上司的舞会题目传送门~思路剖析状态定义\(dp_i\)表示的是以\(i\)为根节点的子树所获得的最大价值。由于每个节点代表着一位人物，有来与不来两种状态，所以再加一维状态变量。\(dp_{i,0}\)表示以\(i\)为根节点的子树所能获得的最大价值，且这位人物没来。\(dp_{i,1}\)则对应来了的状态。状态转移方程现在有个周年庆宴会，宴会每邀请来一个
前言今日偶然打开\(oi-wiki\)，发现树形\(DP\)例题正好是之前在洛谷上鸽着的一道题。所以......\(\color{red}{很高兴以这样的方式认识你，树形DP!}\)这例题造的太好了，简直是无痛入门（感动.jpg）P1352没有上司的舞会题目传送门~思路剖析状态定义\(dp_i\)表示的是以\(i\)为根节点的子树所获得的最大价值。由于每个节点代表着一位人物，有来与不来两种状态，所以再加一维状态变量。\(dp_{i,0}\)表示以\(i\)为根节点的子树所能获得的最大价值，且这位人物没来。\(dp_{i,1}\)则对应来了的状态。状态转移方程现在有个周年庆宴会，宴会每邀请来一个
Loj链接：接竹竿${\scr\color{SkyBlue}{\text{Solution}}}$题目大意：给定一个数组，每次加入一种颜色的数，可以取走与它颜色相同的两个数之间的所有数，问最后取走的所有数中最大和是多少分析：第一眼看到的是二分答案，但不知道二分的check()函数怎么写。没办法，考虑DP（其实是因为我贪心写挂了）DP如果可以，那么要至少要满足一下几个条件：DP前面的选择情况不影响后面的选择情况（前不影响后）DP可以转移时间、空间复杂度等可以以后慢慢优化啦！ 尝试一下？尝试列出转移方程：$$dp[i]=max\begin{cases}dp[i-1]&\text{$c_i$}!={
Loj链接：接竹竿${\scr\color{SkyBlue}{\text{Solution}}}$题目大意：给定一个数组，每次加入一种颜色的数，可以取走与它颜色相同的两个数之间的所有数，问最后取走的所有数中最大和是多少分析：第一眼看到的是二分答案，但不知道二分的check()函数怎么写。没办法，考虑DP（其实是因为我贪心写挂了）DP如果可以，那么要至少要满足一下几个条件：DP前面的选择情况不影响后面的选择情况（前不影响后）DP可以转移时间、空间复杂度等可以以后慢慢优化啦！ 尝试一下？尝试列出转移方程：$$dp[i]=max\begin{cases}dp[i-1]&\text{$c_i$}!={
题目链接题目描述一个商人穿过一个N×N的正方形的网格，去参加一个非常重要的商务活动。他要从网格的左上角进，右下角出。每穿越中间1个小方格，都要花费1个单位时间。商人必须在(2N−1)个单位时间穿越出去。而在经过中间的每个小方格时，都需要缴纳一定的费用。这个商人期望在规定时间内用最少费用穿越出去。请问至少需要多少费用？注意：不能对角穿越各个小方格（即，只能向上下左右四个方向移动且不能离开网格）。题目模型子题目：摘花生因为要在（2N-1）个单位时间穿越出去，而从（1，1）走到（n，n）正好需要（2N-1）个单位时间，所以不能走回头路。题目代码#include#include#includeusin
题目链接题目描述一个商人穿过一个N×N的正方形的网格，去参加一个非常重要的商务活动。他要从网格的左上角进，右下角出。每穿越中间1个小方格，都要花费1个单位时间。商人必须在(2N−1)个单位时间穿越出去。而在经过中间的每个小方格时，都需要缴纳一定的费用。这个商人期望在规定时间内用最少费用穿越出去。请问至少需要多少费用？注意：不能对角穿越各个小方格（即，只能向上下左右四个方向移动且不能离开网格）。题目模型子题目：摘花生因为要在（2N-1）个单位时间穿越出去，而从（1，1）走到（n，n）正好需要（2N-1）个单位时间，所以不能走回头路。题目代码#include#include#includeusin
题目链接：http://poj.org/problem?id=1260具体思路：首先，所需珍珠的数目是固定的，而且每种珍珠所需的数目，可以使用比此种珍珠珍贵(就是价格高的)的珍珠所替代，其次，题目所给珍珠的顺序是按价格由低到高给的，我们可以发现一个规律，珍珠不能隔着种类交换，就是说假设一共三类珍珠，第一种如果需要用第三种替代的话，那么第二种也必须被第三种替代，如果不这么做的话那么第二种需要单独支付额外费用，那么此时，显然如果把第一种用第二种替代更合适，花费更少。这只是说明了珍珠不能隔着替换。我们可以求前i种珍珠所花费的最少费用，那么第i种珍珠所花费的费用可以有多种选择，我们需要求出多种选择中所
