题目描述

原题地址:COGS 洛谷

思路

第一问很简单,最长下降子序列问题,第二问的统计方案数有点意思。

DP方程

阅读全文

题目描述

原题地址:COGS

思路

本来没有什么想法,搜了一下题解之后发现一个很妙的方法,将字符串正反各读一遍,然后求最长公共子序列的长度,最后再用总长度减一下就可以了

阅读全文

题目描述

题目地址:COGS

这题真是蛇,调一晚上。。码力太弱了qwq

思路

本来以为这跟HAOI2016的食物链一样,但是在WA了一次后注意到食物链计算的是经过某点的路径条数,而本题是经过某边的路径条数。

DP 方程

为了求出经过某一条边的的路径条数,可以这样:

设$f(u,v)$是经过边$u,v$的路径条数,$dp(u)$为从源点到$u$的路径条数,$rdp(v)$为从$v$到终点的路径条数,则有 $f(u,v)=dp(u)\times rdp(v)$ 最后的答案就是$\max{f(u,v)} u,v\in G$ 为了实现这个操作,我们先正常建图,求出$rdp(u)$,再反向建图,求出$dp(v)$,最后对于每一条边都合并一下答案即可。

阅读全文

题目描述

原题地址:COGS

一句话题意:二维的分组背包

DP方程

状态定义

令$f(i,j,k)$为在前$i$个箱子中取药,使得生命值为$j$,精神值为$k$ 。

令第$i$瓶药造成的生命值伤害是$pain(i)$,精神伤害是$san(i)$,痛苦值为$suff(i)$。

阅读全文

[COGS 131][USACO Mar08] 奶牛渡河

题目地址:COGS

DP方程

令$dp(i)$为前$i$头牛渡河的最短时间,$m(i)$为一次带$i$头牛过河所花费的时间,则有方程: $$ dp(i)=\min_{2\leq 2j\leq i}{dp(j)+dp(i-j)+m(0),m(i)} $$

对方程的解释

$2\leq 2j\leq i$等价于$1\leq j\leq i-j$ ,即枚举与前面的牛分成一组过河所需时间,然后取最小值

阅读全文

题目描述

问题:题目地址

Vladik often travels by trains. He remembered some of his trips especially well and I would like to tell you about one of these trips:

阅读全文

题目

★★☆
输入文件:zootopia.in 输出文件:zootopia.out 简单对比

时间限制:1 s 内存限制:32 MB

【题目描述】

  1. 物理学要求:为了稳定和美观,半径大的蛋糕必须在放在半径小的蛋糕下面。
  2. Mr.Big的钦定要求:编号小的蛋糕必须放在编号大的蛋糕下面。

你需要帮他制定一个使多层蛋糕总体积最大的方案。

你只需要计算出最大的总体积即可。 注意:两个半径相同的蛋糕不能放在一起

【输入格式】

第一行一个整数n,

接下来n行,第i+1行两个整数R,H分别表示编号为i的蛋糕的半径和高度。

【输出格式】

只有一行一个整数,为最大总体积,由于出题人懒得写评测插件,你需要精确到小数点后2位

题解

思路

此题乍一看是普通的最长上升/下降子序列,然而$O(n^2)$的做法会挂掉,所以要用$O(nlogn)$的做法

阅读全文