zcmimi's blog

arrow_back动态规划共95篇文章

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

f[i][j]表示状态为i,上一个吃的是第j道菜

f[i'][k]=\max(f[i'][k],f[i][j]+a[j]+d[j][k]) (d[j][k]表示连续吃j,k能额外获得多少满意度)

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

如果没有时间限制那就是一个裸的完全背包

我们可以先按时间从大到小排序,保证如果选了后面作业能选的话不会影响当前作业

接着背包求出每天的最小花费

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

f_i为前i个最小代价

s_i为前i个字符串总字符数

f_i=\min(f_j+|(s_i-s_j)+(i-j-1)-L|^p)

可以发现这个方程有决策单调性

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

f[i][k]为第i位,分成k

f[i][k] = MAX(f[j][k-1] + cnt[j+1][i])

这样的话肯定复杂度爆炸

既然看到MAX,那是不是可以用线段树优化呢?

记录每个点贡献的范围,更新时把这个范围的点++就可以了。

相信看代码可以看懂

其实我还加了滚动数组OwO

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

有趣的题

先倍增处理出len_x一个点最长往上跳多少个

然后动态规划

dp_x为在放置最少的情况下x还能再向上跳多少个

那么dp_x = \max(f[to])-1

如果dp_x = -1,那么在选中++ans_x,dp_x = len_x-1

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

f[i][j]表示翻转i次,还有j个与目标状态不同位置的方案数

每次翻转可以使与目标状态不同位置数量改变

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

g_i表示交集个数至少为i的方案数

那么g_i = {n\choose i}(2^{2^{n-i}}-1)

先从n中选i个,然后其他可以随便取

那就是有2^{n-i}个集合可以取

然后又可以取至少1个集合

那么答案就是{n\choose i}(2^{2^{n-i}}-1)

f_i表示恰好为i

那么g_k=\sum_{i=k}^n f_i\cdot {i\choose k}

反演f_k=\sum_{i=k}^n g_i\cdot{i\choose k} (-1)^{i-k}

不能直接快速幂,因为指数不能\mod p,要用2^{2^i}=(2^{2^{i-1}})^2倒着枚举算

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

f_{t,i,j} = MAX(f_{t-1,x',y'})+1

复杂度:O(Tnm),只能过50%

看到k \le 200那么我们是不是可以直接用?

f_{k,i,j}为在区间k中在位置(i,j)能最多滑行多远

f_{k,i,j} = MAX(f_{k-1,i,j},f_{k-1,i',j'}+dis_{(i,j),(i',j'))})

那么复杂度就是O(kn^3),可以用单调队列优化掉其中一个n

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

考虑排序后的序列

i个人说有a_i个人分数比他高,有b_i个分数比他低

从大到小排序后分数和i相同的人的区间为[a_i+1,n-b_i]

我们设L_i = a_i + 1, R_i = n - b_i

那么如果L_i > R_i显然是假话

如果R_i-L_i+1小于这个区间的人数(L_{i'}=L_iR_{i'}=R_i),那么这也是假话

去掉所有一定是假的话后,问题变成:给若干个区间[l_i,r_i],价值为v_i,从中选出若干个没有交集的区间,价值和最大为多少?

8/10
Search
search