dp – 第5页 – Tgotp-Blog

【bzoj1068】&& 洛谷2470 [SCOI2007]压缩 区间dp

思路:区间dp

具体实现:

f[i][j][k] 代表区间 i - j 间是否存在m;

另默认在i-1处有一个M;

当s[mid+1,r]==s[l,mid]时,f[i][j][0] = f[i][(i+j)/2][0] + 1;

当中间加入了M,枚举M放在哪里就可以;[......]

Read more

[ZJOI2007]棋盘制作 BZOJ1057 && luogu1169

思路: dp (做了好久,还是太弱了)

做法:求出每个点开始的最大高度及向左向右扩展的最大长度,然后从每个点开始枚举求出ans1,ans2;

注意:求得l,r包含了该点,所以操作时要 -1;

c++代码如下:

&[......]

Read more

NOIP2015 P2679 子串

动态规划,原谅我学的渣,只能边看题解边做。

用 f[j][p] 数组表示到 s2 的分割了p次的情况(上一次到当前没分,所以匹配到s [i]!=s[j]时,要清零)。

用dp[j][p]数组表示到s2的分割了p次的情况(这次结尾断开)。

小细节,j 从后往前匹配,为了避免冲突(免去[......]

Read more

【bzoj1023】[SHOI2008]cactus仙人掌图

并没有自己实现。

大概理了一下思路就粘贴了。

阐述一下我的观点:

首先根据原有的条件连边,然后根据题目,可以清晰的发现只有一条链,所有的回路都在链上;

然后dfs,可以发现在某个进入回路的点上最远的点才可能在直径的端点上,然后链上某一个点可能连了多个回路,取最值。

然后[......]

Read more

【bzoj1911】[Apio2010]特别行动队commando

首先读题后第一感觉这是个dp;

然后我们继续看到方程 =》一般来说这种题就可以用斜率优化了。

然后我们很容易推导得到f[i] = max(f[j]+a(s[i]-s[j])^2+b(s[i]-s[j])+c;

设k < j且j优于k;

即有:f[j]+a(s[i]-s[[......]

Read more

【bzoj1010】[HNOI2008]玩具装箱toy

 

【bzoj1597】[Usaco2008 Mar]土地购买

思路:斜率优化dp。

这种题一般自己推一推比较好;

简单的,我们可以看出,

首先:对于x排序,可以提出某些被包含的土地块(直接打包买)

然后:可以发现dp思路:f[i] = min(f[j]+b[j+1].y*b[i].x

但是可以很容易发现时间不够;

继续发现可[......]

Read more

3156: 防御准备

斜率优化

f[i] = min((i-j-1) * (i-j)/2 + f[j]) + data[i]

f[i] = min((i-1)* (i-j)/2 -j * (i-j)/2 + f[j]) + data[i]

f[i] = min(j -2*i*j+j*j + f[j]*2[......]

Read more

疯狂的火神

有优先条件的背包dp,就是说,对于背包 a,b,若a优先级大于b且 a,b最后都要选,就选先放a后放b。

题面

代码