P11311 漫长的小纸带题解

题意

给定一个长为

n

数组

a

，将他分成若干段，每段的代价为这一段数字个数的平方，求最小代价。

思路

看到分段、最小代价这些字眼，于是考虑 dp：

设

dp_i

表示

1

到

i

的最小代价，

s_{i,\,j}

为

i

到

j

的不同数字个数。

考虑这个状态可以由那些状态得来，发现可以枚举

i

所在块的长度

k

，此时

dp_i=dp_{i-k}+s_{i,\,j}^2

，状态转移方程有了，便可 dp，复杂度

O(n^2)

，能拿 32pts（卡常可卡到 48pts）

考虑怎么优化，我们发现当我们考虑

1

到

i

时，如果分成

i

块，则总代价为

i

，所以不可能存在某一块的数字个数大于

\sqrt i

，所以我们枚举

k

的时候，有用的

k

仅当：

当前块数字个数不大于 $\sqrt i$ ；
当前块大小为 $k+1$ 时数字个数会增加（否则 $k+1$ 一定更优）

于是我们可以改变枚举方法，令以

j

为右端的块，数字种类数为

i

，块的左端点最左到

pre_{i,\,j}

。这个东西的大小只有

n\sqrt n

，也可以通过双指针

O(n\sqrt n)

求。

于是我们有了新的转移方程：

\large dp_{i,\,j}=\large \max_{j=1}^{\lfloor\sqrt i\rfloor}dp_{pre_{j,\,i}-1}+j^{2}

Code

CPP

#include <bits/stdc++.h>
using namespace std;

constexpr int maxn = 200010;

int n, a[maxn], l, r, pre[490][maxn], sum, dp[maxn], ls[maxn], tot, t[maxn];
map <int, int> v;

void pu(int x) {//加入
	if (!(t[x]++)) {
		sum++;
	}
	return ;
}
void po(int x) {//删除
	if (!(--t[x])) {
		sum--;
	}
	return ;
}

signed main() {
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	
	cin >> n;//读入
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		ls[i] = a[i];
	}
	
	sort(ls + 1, ls + 1 + n);//本做法必须离散化，要不然双指针就TLE了
	ls[0] = 0;
	for (int i = 1; i <= n; i++) {
		if (ls[i] != ls[i - 1]) {
			v[ls[i]] = ++tot;
		}
	}
	for (int i = 1; i <= n; i++) {
		a[i] = v[a[i]];
	}
	
	for (int i = 1; i <= sqrt(n); i++) {//双指针求pre
		l = 1, r = 0;
		sum = 0;
		for (int j = 1; j <= tot; j++) {
			t[j] = 0;
		}
		for (int j = 1; j <= n; j++) {
			pu(a[++r]);
			while (sum > i) po(a[l++]);
			pre[i][j] = l;
		}
	}
	
	dp[1] = 1;
	for (int i = 2; i <= n; i++) {//dp转移
		dp[i] = maxn;
		for (int j = 1; j <= sqrt(i); j++) {
			dp[i] = min(dp[pre[j][i] - 1] + j * j, dp[i]);
		}
	}
	
	cout << dp[n];//输出
	
	return 0;
}

题解：P11311 漫长的小纸带

文章操作

P11311 漫长的小纸带题解

题意

思路

Code

相关推荐

评论

题解：P11311 漫长的小纸带

文章操作

P11311 漫长的小纸带 题解

题意

思路

Code

相关推荐

评论

P11311 漫长的小纸带题解