设计素材网站情人节,亚马逊网站特点和经营范围,济南专业网站建设咨询,云阿里云做网站D:圆
正着求删除的最小代价不好做#xff0c;采用逆向思维#xff0c;求选择一些不相交的线段使得构成一个圆的代价尽量大#xff0c;最后答案就是所有线段权值之和减去最大代价。
那么如何求这个最大代价呢#xff1f;显然区间DP
老套路#xff1a;破环成链#xff0…D:圆
正着求删除的最小代价不好做采用逆向思维求选择一些不相交的线段使得构成一个圆的代价尽量大最后答案就是所有线段权值之和减去最大代价。
那么如何求这个最大代价呢显然区间DP
老套路破环成链枚举区间长度 len 枚举区间左端点 i 和右端点 j
很明显没有线段长度为1故len从2开始
具体的
线段的操作和点的相似但又不完全相同具体看代码即可。
1不选择以左端点的线段
2、选择以为左端点的线段。枚举左端点 所能到达的右端点 v权值为 w那么当前的答案
由 区间 的答案加上 区间 的答案加上线段 的权值构成即 int n, m;
int f[M][M]; // f[i][j] 区间i到j不相交边的最大价值
vectorPII g[N];
void solve()
{cin n m;int s 0;for (int i 1; i m; i){int x, y, w;cin x y w;if (x y)swap(x, y);g[x].pb({y, w});g[y].pb({x n, w});s w;}for (int len 2; len 2 * n; len){for (int i 1; i len - 1 2 * n; i){int j i len - 1;f[i][j] f[i 1][j]; // 不选择以i为左端点的线段for (auto ed : g[i]) // 选择以i为左端点的线段{int v ed.xx, w ed.yy;if (v j) // 已经越过右端点了continue;if (v - 1 i 1) //区间端点不能相同w f[i 1][v - 1];if (j v 1)w f[v 1][j];f[i][j] max(f[i][j], w);}}}int tmp 0;for (int i 1; i n; i)tmp max(tmp, f[i][i n - 1]);s s - tmp;cout s endl;
}
类似的题目
Codeforces Round 661 (Div. 3)
F. Yet Another Segments Subset
两个题目非常相似但是又不完全相同。
本题的数据显然如果直接区间dp会超时但是n却是很小我们想能不能进行离散化。
本题的相交比较上一题有点不同不同在包含的时候端点可以相交而不包含时端点不可相交。
很明显离散化候不同区间值被拉近了距离但是不相交得还是不相交所以本题可以离散化。(具体题目具体分析有的题目可能会有坑
状态表示 表示区间 里面满足题意得最大区间数量。
然后我们就想一下转移方程
具体的还是区间DP的过程枚举区间长度 len 枚举区间左端点 i 和右端点 j
我们还是以选不选以 为左端点的区间
1不选
2:选
我们看第二个方程很明显就是我们上面说的
即只有完全包含端点才可以相同
我们还要注意一种情况那就是区间恰好等于 ,这种情况由于 ,被跳过了
所以最后加上个数即可完成。
int n;
PII p[N];
vectorint g[N];
void solve()
{vectorint t;cin n;for (int i 1; i n; i){int l, r;cin l r;p[i] {l, r};t.pb(l);t.pb(r);}sort(t.begin(), t.end());t.erase(unique(t.begin(), t.end()), t.end());for (int i 1; i n; i){int x lower_bound(t.begin(), t.end(), p[i].xx) - t.begin() 1;int y lower_bound(t.begin(), t.end(), p[i].yy) - t.begin() 1;g[x].pb(y);}int m t.size();vectorvectorint f(m 10, vectorint(m 10));for (int len 1; len m; len){for (int i 1; i len - 1 m; i){int j i len - 1;f[i][j] f[i 1][j];int cnt 0;for (auto ed : g[i]){int v ed;if (v j)cnt;if (v j)f[i][j] max(f[i][v] f[v 1][j], f[i][j]);}f[i][j] cnt;}}cout f[1][m] endl;for (int i 0; i m 1; i)g[i].clear();
}
