AT_cf16_exhibition_final_f Intervals 题解

博客园，博客园，我们马上就到：AT_cf16_exhibition_final_f Intervals 题解 - Add_Catalyst - 博客园 (cnblogs.com)。

知识点

贪心，DP。

分析

可以证明有一个区间一定不动，分奇偶即可。

接下来很直观地可以感受到要把区间分到两边，且短的放在离不动区间近的会更优，所以我们降序排序。

进一步地，把区间对半分开放到左右也会让答案不劣，这就与初中的绝对值问题类似。

我们可以列出答案的表达式：设左边选到了第

i

个，右边选到了第

j

个。

不动的区间，设为 $(L_x,R_x)$ ，贡献为 $0$ 。
放到左边的区间，设为 $(L_{1,i},R_{1,i})$ ，贡献为 $(i-1)(R_{1,i}-L_{1,i})+(R_{1,i}-L_x)$ 。
放到右边的区间，设为 $(L_{2,j},R_{2,j})$ ，贡献为 $(j-1)(R_{2,j}-L_{2,j})+(R_x-L_{2,j})$ 。

那么可以考虑拆贡献，这里要分为奇偶两种情况：

$n$ 为奇数：

那么较为简单，设 $m=\lfloor \frac{n}{2} \rfloor$ ，左边和右边各会选 $m$ 个区间。贡献为：
$\sum_{i}[(i-1)(R_{1,i}-L_{1,i}) + R_{1,i}] + \sum_{j}[(j-1)(R_{1,j}-L_{1,j}) - L_{1,j}] + m(R_x-L_x) \\$
$n$ 为偶数：

考虑不动的区间随意取中间两个其中一个即可。设 $m=\lfloor \frac{n}{2} \rfloor$ ，左边取 $m-1$ 个，右边取 $m$ 个。贡献为：
$\sum_{i}[(i-1)(R_{1,i}-L_{1,i}) + R_{1,i}] + \sum_{j}[(j-1)(R_{1,j}-L_{1,j}) - L_{1,j}] + mR_x-(m-1)L_x \\$

那么 DP 状态就是

f_{l,r,0/1}

表示左边选了

l

个，右边选了

r

个，

0/1

表示是否已经选取了不动的区间，如果空间不够考虑滚动数组优化。

剩下的转移从上面即可推出，复杂度

O(n^2)

。

代码

CPP

constexpr int N(5e3+10);

int n,L,R;
struct node {
	int l,r;
	node(int l=0,int r=0):l(l),r(r) {}

	void Input() { scanf("%d%d",&l,&r),l=-l; }

	int len() { return r-l; }

	friend bool operator <(node a,node b) { return a.len()>b.len(); }
} a[N];
ll f[N>>1][2],_f[N>>1][2];

signed main() {
	/*DE("Input");*/
	scanf("%d",&n),L=(n-1)>>1,R=n>>1;
	FOR(i,1,n)a[i].Input();
	sort(a+1,a+n+1);
	/*DE("DP");*/
	FOR(l,0,(n+1)>>1)f[l][0]=f[l][1]=LINF;
	f[0][0]=0;
	FOR(i,1,n) {
		FOR(l,0,min(i,L))_f[l][0]=_f[l][1]=LINF;
		FOR(l,0,min(i-1,L)) {
			int r((i-1)-l);
			if(l<L)tomin(_f[l+1][0],f[l][0]+(ll)l*a[i].len()+a[i].r);
			if(r<R)tomin(_f[l][0],f[l][0]+(ll)r*a[i].len()-a[i].l);
			tomin(_f[l][1],f[l][0]+(ll)R*a[i].r-(ll)L*a[i].l);
		}
		FOR(l,0,min(i-2,L)) {
			int r((i-1)-l-1);
			if(l<L)tomin(_f[l+1][1],f[l][1]+(ll)l*a[i].len()+a[i].r);
			if(r<R)tomin(_f[l][1],f[l][1]+(ll)r*a[i].len()-a[i].l);
		}
		swap(f,_f);
	}
	/*DE("Output");*/
	printf("%lld\n",f[L][1]);
	return 0;
}

题解：AT_cf16_exhibition_final_f Intervals

文章操作

AT_cf16_exhibition_final_f Intervals 题解

知识点

分析

代码

相关推荐

评论

题解：AT_cf16_exhibition_final_f Intervals