dp – Tgotp-Blog

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

1019: [SHOI2008]汉诺塔

令f[i][j]表示第i个位置移动j个盘子到另外一个盘子上的步数。

令g[i][j]表示第i个位置移动j个盘子所到达的盘子。

 

c++代码如下:

 

P2258 子矩阵

暴力枚举选行的情况,然后dp求选列的最优情况。

f[i][j]表示选了i行,最后一次选的是j列的情况。。。

c++代码如下:

 

1592: [Usaco2008 Feb]Making the Grade 路面修整

按排序后的数组来搞一搞就好了。

枚举上一次选某种情况下的最小话费,同时可以加个优化,

即f[i][j]表示在第i个点,在b中选>=j 的编号的点的最小话费。

g[i][j]表示在第i个点,在b中选<=j 的编号的点的最小话费。

1:c++代码如下:
[crayo[......]

Read more

3039: 玉蟾宫

和以前做过的某道题有点像(好吧其实就是退化题)

令l[i][j]为能向左延伸的最大长度,r[i][j]同理up[i][j]代表向上最大延伸长度,

然后枚举每一个点就搞定了。

c++代码如下: