夏晓光(loveJY)的博客

"念念不忘,必有回响"

CSP原题...

拿到题就很决策单调性优化?

首先我们有$dp[i][j]$表示的是这一段为i上一段为j的最小代价是什么

转移时枚举之前的某个点,然后再枚举之前那个点上一段,再判断合不合法即可

你会发现这个东西是有决策单调性的,也就是说我们能多分就多分一定更优

所以我们可以考虑用一个一维...dp[i]表示考虑了前i个数的最优代价

那么显然我们可以记录某个状态的转移点啊,$pre_i$表示点i是从哪个状态转移而来的

然后如果$sum[j]-sum[pre[j]]$<$sum[i]-sum[j]$就可以,然后找到最大的j就是i的转移点...

$sum_j-sum_{pre[j]}$表示单调队列值,我们就可以用单调队列来维护下,队头可以用这个判断

但是我们队尾怎么搞呢?单调队列的性质就是值小而且时间靠后就是更优的

那么$sum_j-sum_{pre[j]}$就可以用单调队列来判断这个来删掉队尾QWQ

这样我们用这个就可以直接解决转移点了

之后就可以用__int128卡常了

code:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=4e7+7;
const int MAXM=1e5+7;
const int P=(1<<30);
int n,typ,x,y,z,m;
int a[MAXN],b[MAXN],p[MAXM],l[MAXM],r[MAXM],q[MAXN],pre[MAXN];
ll sum[MAXN];
inline ll d(int x) {
	return sum[x]-sum[pre[x]];
}

int main() {
	scanf("%d%d",&n,&typ);
	register int i,j;
	if(typ) {
		scanf("%d%d%d%d%d%d",&x,&y,&z,&b[1],&b[2],&m);
		for(i=1; i<=m; ++i)scanf("%d%d%d",&p[i],&l[i],&r[i]);
		for(i=3; i<=n; ++i)b[i]=(0ll+1ll*b[i-1]*x+1ll*b[i-2]*y+z)%P;
		for(i=1; i<=m; ++i) {
			for(j=p[i-1]+1; j<=p[i]; ++j) {
				a[j]=(b[j]%(r[i]-l[i]+1))+l[i];
				sum[j]=sum[j-1]+a[j];
			}
		}
	} else {
		for(i=1; i<=n; ++i)scanf("%d",&a[i]),sum[i]=sum[i-1]+a[i];
	}
	int h,t;
	q[h=t=0]=0;
	for(i=1; i<=n; ++i) {
		while(h<t&&d(q[h+1])+sum[q[h+1]]<=sum[i])++h;
		pre[i]=q[h];
		while(h<t&&d(q[t])+sum[q[t]]>=d(i)+sum[i])--t;
		q[++t]=i;
	}
	int nw=n;
	__int128 ans=0,tmp=1;
	while(nw) {
		tmp=d(nw);
		tmp*=d(nw);
		ans+=tmp;
		nw=pre[nw];
	}
	int st[50],tp=0;
	while(ans) {
		st[++tp]=ans%10;
		ans/=10;
	}
	while(tp)printf("%d",st[tp--]);
	return 0;
}