孝义做网站,wordpress 腾讯视频插件下载,网站界面可以做版权吗,企业展厅建筑problem
LOJ2772
solution
这道题求的是“保证最多”#xff0c;这个“保证”真的屑啊#xff01;
因为我们无法确定实验生成的克数#xff0c;所以我们应当计算的是最坏情况。
又因为我们可以选择做哪些实验#xff0c;所以要的是所有实验组合最坏情况下的最大价值。…problem
LOJ2772
solution
这道题求的是“保证最多”这个“保证”真的屑啊
因为我们无法确定实验生成的克数所以我们应当计算的是最坏情况。
又因为我们可以选择做哪些实验所以要的是所有实验组合最坏情况下的最大价值。
如果题目读错成直接求最多那么就会写出线段树优化 dpdpdp结果样例都过不了 将答案数学化长相表示出来设 dpi:dp_i:dpi: 已经装了 iii 克反物质最大保证还能获得多少价值。
转移有dpimax1≤j≤n{minlj≤k≤rj{dpik1e9⋅k−cj}}dp_i\max_{1\le j\le n}\Big\{\min_{l_j\le k\le r_j}\{dp_{ik}1e9·k-c_j\}\Big\}dpimax1≤j≤n{minlj≤k≤rj{dpik1e9⋅k−cj}}。答案即为 dp0dp_0dp0。
其实只要搞清楚这一点列出这个转移剩下的优化部分已经是非常简单的了。
k∈[lj,rj]→ik∈[ilj,irj]k\in[l_j,r_j]\rightarrow ik\in[il_j,ir_j]k∈[lj,rj]→ik∈[ilj,irj]这浓浓的滑动窗口味儿。
稍微改写一下初始化 dpi1e9⋅idp_i1e9·idpi1e9⋅idpimax1≤j≤n{minlj≤k≤rj{dpik}−cj}dp_i\max_{1\le j\le n}\Big\{\min_{l_j\le k\le r_j}\{dp_{ik}\}-c_j\Big\}dpimax1≤j≤n{minlj≤k≤rj{dpik}−cj}。
然后对每个实验都开一个维护递增的单调队列用队首更新答案。
i−−i--i−−弹出单调队列中不在 [ilj,irj][il_j,ir_j][ilj,irj] 的元素每次都要新加 iljil_jilj。
这些都是套路时间复杂度 O(na)O(na)O(na)。
code
#include bits/stdc.h
using namespace std;
#define maxn 105
#define maxv 2000005
#define int long long
const int NB 1e9;
int n, a;
int l[maxn], r[maxn], c[maxn];
int f[maxv 1];
deque pair int, int q[maxn];signed main() {scanf( %lld %lld, n, a );for( int i 1;i n;i ) scanf( %lld %lld %lld, l[i], r[i], c[i] );for( int i a 1;i (a 1);i ) f[i] -1e18; //将爆出实验的设为极小值 就不会被误判为答案for( int i a;~ i;i -- ) {f[i] NB * i;for( int j 1;j n;j ) {//[il(j),ir(j)] 才会对i产生贡献 且是这段里的最小值贡献//il(j) 在i1容量中没有被计入 这里计入while( ! q[j].empty() and q[j].back().second f[i l[j]] ) q[j].pop_back(); //维护单增队列q[j].push_back( make_pair( i l[j], f[i l[j]] ) );while( ! q[j].empty() and q[j].front().first i r[j] ) q[j].pop_front(); //弹出不在范围内的f[i] max( f[i], q[j].front().second - c[j] ); //实验是可以选的 所以外层dp比较取较大值}}printf( %lld\n, f[0] );return 0;
}
