区间dp – Tgotp-Blog

P2858 [USACO06FEB]奶牛零食Treats for the Cows

令f[i][j]表示正向选到第i个,倒向选到第j个点,

那么 f[i][j] = max(f[i - 1][j] + a[i] * (i + j),f[i][j - 1] + a[n - j + 1] * (i + j));

c++代码如下:
[crayon-5b50ae204cce2[......]

Read more

1202: [HNOI2005]狡猾的商人

清一色的并查集,我写了一个区间dp。

令f[i][j]代表i-j的区间话费,枚举断点k来看是否可以得到i-j的话费,若i-j本身存在价值,就比较,如果不一样输出false直接返还。

如果一直没有false就输出true

c++代码如下:
[crayon-5b50ae204d8eb[......]

Read more

1090: [SCOI2003]字符串折叠

区间dp。

f[i][j]代表i-j区间最短长度。

然后随便弄弄就好了。

f[i][j] = min(f[i][k],f[k+1][j],f[i][j]);

然后i - k 是 i - j 的可压缩情况时

f[i][j] = min(f[i][j],f[i][k] +[......]

Read more

BZOJ1925 [SDOI2010]地精部落

题解传送门: http://www.cnblogs.com/huangdalaofighting/p/7358616.html

c++代码如下:

 

加分二叉树

洛谷没有spj,有点坑啊,当成最小字典序输出吧...

首先中序遍历代表对于一个数x,其序列左边是它的左子树,右边是它的右子树

f[i][j]代表i - j区间内最大值,node[i][j] 代表i - j 内区间最大值时的根节点...

搞定.

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

Read more

BZOJ1084 [SCOI2005]最大子矩阵

三维数组f[i][j][s]表示,第一列到i第二列到j有s个矩阵的最优情况。

更新的时候对于分成在一边加或者同时两边加就这样。

c++代码如下:

 

Polygon poj1179

Polygon

Time Limit: 1000MS

Memory Limit: 10000K

Total Submissions: 5700

Accepted: 2458

Description

Polygon is a game f[......]

Read more

【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