夏晓光(loveJY)的博客

CSP D2T2

这...好神似啊QAQ?

我们要最少的操作次数使得合并后的序列单调不降

如果写出一个dp,$f_{i,j}$表示考虑前i个数最后一刀砍在j处的最小代价是什么,然后直接dp即可

所以可以发现这个东西具有决策单调性....等等是贪心吧?

你会发现$g_i$表示前i个数我们最小分割次数下最后一段最小是多少

然后f_i转移的时候只需要枚举到前面的一个j满足$g_j<=sum_i-sum_j$即可

所以就做完了,直接写break优化就能2e5飞快了!

期望复杂度$O(n^2)$,实际复杂度$O(n)$

code:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=3e5+7;
ll f[MAXN],sum[MAXN],pre[MAXN];
int a[MAXN],n;

int main() {
	scanf("%d",&n);
	for(int i=1; i<=n; ++i) {
		scanf("%d",&a[i]);
		sum[i]=sum[i-1]+a[i];
//		printf("%lld?\n",sum[i]);
	}
	memset(f,0x3f3f3f3f,sizeof(f));
	f[0]=0;
	for(int i=1; i<=n; ++i) {
		for(int j=i-1; j>=0; --j) {
			if(pre[j]<=sum[i]-sum[j] && (f[j]+i-j-1<f[i])) {
				f[i]=f[j]+i-j-1;
				pre[i]=sum[i]-sum[j];
				break;
			}
		}
	}
	printf("%lld\n",f[n]);
	return 0;
}

还有一题,一样的break剪枝,过$1e5$
P4954 [USACO09OPEN]Tower of Hay G

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=3e5+7;
ll f[MAXN],sum[MAXN],pre[MAXN];
int a[MAXN],n;

int main() {
	scanf("%d",&n);
	for(int i=1; i<=n; ++i) {
		scanf("%d",&a[i]);
//		printf("%lld?\n",sum[i]);
	}
	reverse(a+1,a+n+1);
	for(int i=1; i<=n; ++i) {
		sum[i]=sum[i-1]+a[i];
	}
	memset(f,0,sizeof(f));
	f[0]=0;
	for(int i=1; i<=n; ++i) {
		for(int j=i-1; j>=0; --j) {
			if(pre[j]<=sum[i]-sum[j] && (f[j]+1>f[i])) {
				f[i]=f[j]+1;
				pre[i]=sum[i]-sum[j];
//				printf("%lld %lld\n",pre[i],f[i]);
				break;
			}
		}
	}
	printf("%lld\n",f[n]);
	return 0;
}