dp – Tgotp-Blog

F. Leaf Sets

F. Leaf Sets
time limit per test

3 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Yo[......]

Read more

4247: 挂饰

容易贪心的想到,既有挂钩又有正价值的点一定能加入,即可以把这个挂在手机上,把原来的接上去。

做这一步的时候要考虑原来是否已经有加入,有的话挂钩量要减一。

然后考虑对于负价值的点,令f[i]表示能提供i个挂钩的最小价值,做一遍dp

然后和原来的合并即可,因为原来的是按顺序加入,那么扫[......]

Read more

2018年9月28日 0 / /
Tag: 

4861: [Beijing2017]魔法咒语

首先有不能含某个子串,那么容易发现使用ac自动机解决

对于前60%数据:

令f[i,j]表示构造到了第i个位置,目前位于ac自动机的第j个节点上。

有f[i+len[v]][to] += f[i][j]

那么很容易解决掉了这部分数据。

对于后40%数据:

因为考虑[......]

Read more

4576: [Usaco2016 Open]262144

直接放聊天记录了...

Tgotp 2018/5/5 21:37:43

令f[i][j]表示

Tgotp 2018/5/5 21:37:55

第i个位置构成j需要几个位置

Tgotp 2018/5/5 21:38:07

首先

Tgotp 2018/5[......]

Read more

2018年5月5日 0 / /
Tag: 

5248: [2018多省省队联测]一双木棋

容易写出暴力.
c++代码如下:

上述代码50分.
考虑如何优化
发现其实每一层当前能选的都是固定的.
那么考虑状压来表示出每一层的状态.
因为m最大为10,根据题意显然总变化不会超过10
用1表示向左边移动,0表示该[......]

Read more

1633: [Usaco2007 Feb]The Cow Lexicon 牛的词典

令f[i]表示前i个字符中最多匹配多长,那么对于每个位置暴力匹配即可。

树状数组维护一下前i个当中最大的f[j]

c++代码如下:

 

1672: [Usaco2005 Dec]Cleaning Shifts 清理牛棚

考虑令f[i]表示至少把前i个点打扫了所需要的最小花费,

那么对于第i个奶牛打扫的即为f[a[i].e] = min(f[a[i].s-1]+a[i].w);

考虑更新了f[a[i].e]实际上也对于前a[i].e个点均有影响,所以还需对f[j]取min j < a[i].e[......]

Read more

Count Arrays

Count Arrays

Time limit: 1000 ms
Memory limit: 256 MB

You are given Q segments. For every 1 \le i \le Q, segment number i is [l_i,[......]

Read more

#185. 【ZJOI2016】小星星

考虑的f[i][j]表示第i个点映射到图中第j个点上(可重)得方案数

树形dp,然后容斥搞一搞就好了。

c++代码如下:

 

3594: [Scoi2014]方伯伯的玉米田

思路明天过来补。。。

其实很好观察发现到一个性质。要保证单调不下降,每次选择的区间右端点一定是n。

(结果发现了这个性质我还是不会做XD

令f[i][j]表示第i个位置用了j次拔高机会最多保留的个数。

那么f[i][j] = f[x][y] + 1 ( a[i] +  j &[......]

Read more