zcmimi's blog

arrow_back动态规划共96篇文章

avatar
zc
2020-01-29 08:06:00
查看原题

点击跳转

avatar
zc
2020-01-28 21:26:00
查看原题

点击跳转

avatar
zc
2020-01-28 17:08:00
查看原题

点击跳转

avatar
zc
2020-01-24 17:26:00
查看原题

点击跳转

将一个骑士与他最痛恨的人连边

先考虑这个如果是树型dp:

f_x表示不取x,g_x表示取x

f_x=\sum \max(f_{to},g_{to}) \\ g_x=\sum f_{to}

我们可以用两次树型dp代替基环树dp

第一次: 选择x,不选择x最痛恨的人

第一次: 选择x最痛恨的人,不选择x

avatar
zc
2020-01-24 16:39:00
查看原题

点击跳转

两次dp解决代替基环树dp

所有的A_i\rightarrow i构成了一棵基环树

我们先考虑如果基环树的子树怎么做

也就是树型dp

(f_x表示不放,g_x表示放)

若元素i不投放,

f_x=\sum_{A_y=x}\max(f_y,g_y)

否则必须至少有一个元素限制i,不能投放

g_x=\max_{A_y=x}\{f_y+\sum_{A_z=x,z\not = y}\max(f_z,g_z)\}

找到环上的一个点,将它和它限制的那个点断开,先后进行两次树形dp,

第一次是假设环上的这个点对其限制的点不起限制作用

另外一次是强制环上那个点已经限制了其可以限制的点(也就是环上那个点不选)

avatar
zc
2020-01-23 12:40:00
查看原题

点击跳转

f[i]=\max{f[t-r]+p}

avatar
zc
2020-01-21 16:39:00
查看原题

点击跳转

排序后动态规划

f[i][j]表示前i个女生,至少有j个比男生高

f[i][j]=(f[i-1][j]+f[i-1][j-1]\times(p-j+1))\times(n-i)!(p表示有p个男生比前i个女生矮)

avatar
zc
2020-01-20 23:48:00
查看原题

点击跳转

按斜率建图

然后跑背包

avatar
zc
2020-01-19 21:11:00
查看原题

点击跳转

f[k][i][j]表示前k种面值,Ai元,Bj元最少交换几张

avatar
zc
2020-01-19 10:55:00
查看原题

点击跳转

f[sta]表示sta表示的所有颜色都排列到从1开始的相连的一段,最少要多少次

pre[i][j]表示所有颜色i前面总共有多少个颜色j,也就是说要将所有颜色i移动到颜色j左边要移动多少次

即:\sum[y<x,c[x]=i,c[y]=j]

sta[i]表示sta表示的第i种颜色的状态

f[sta]=\min{f[sta']+\sum_{sta[j]=1,sta[k]=0}pre[j][k]}

3/10
Search
search