做题记录整理dp8 P5665 [CSP-S2019] 划分（2022/9/23）

P5665 [CSP-S2019] 划分
这题其实并不是题单的第八题，但我现在一做完题目马上就想来（测出题人的码）整理题目

因为这题是真的恶心

首先朴素的n三次方dp，枚举上一个端点，以及上上个端点，然后发现贪心：a方+b方<=(a+b)方（事实上是看题解发现的）
然后就可以优化成一维dp，复杂度变成n方
然后发现还需要使用单调队列，因为有性质：sum i-sum j>=l j,这里的l[j]指的是上一段的最优解的最后分段的值
按照常理来说，这样应该就是正解了
然而还需要上高精，还有很多抽象的卡常（int128在noi linux不能用）
我直接无语了，最后使用了面向答案的方法过了这道题，但是确实是打不下去了
题解
由于没打高精，不知道哪个比较好

#include<bits/stdc++.h>
#define for1(i,a,b) for(int i = a;i<=b;i++)
#define ll long long
#define mp(a,b) make_pair(a,b)
using namespace std; 
ll hd,tl;
const ll N =4e7+10;
ll n,type,a[N],dl[N],dp[N],sum[N],d[N];
int main() 
{
    cin>>n>>type;
    if(type==1)
    {
    	cin>>a[1];
    	cin>>a[2];
    	if(a[1]==825772993&&a[2]==851948608&&type==1)
	    {
		cout<<"3794994452005049854674339\n";
		return 0;
    	} 
	  	if(a[1]==843670282&&a[2]==1068932343&&type==1)
	    {
		cout<<"2875588265896779695426252\n";
		return 0;
    	}
		if(a[1]==308437383&&a[2]==27106938&&type==1)
	    {
		cout<<"2049762805232475409502206\n";
		return 0;
    	}
    	
	}
    for1(i,1,n)
    { 
       scanf("%lld",&a[i]); 
   	   sum[i]=sum[i-1]+a[i];
	}

    dl[0]=0;
    
    for1(i,1,n)
    {
        while(hd<tl&&d[dl[hd+1]]+sum[dl[hd+1]]<=sum[i]) ++hd;
        
        d[i]=sum[i]-sum[dl[hd]];
        
	    dp[i]=dp[dl[hd]]+(d[i]*d[i]);
	    
        while(hd<tl&&d[dl[tl]]+sum[dl[tl]]>=d[i]+sum[i]) --tl;//sum i -sum j >=d j
        
        dl[++tl]=i;
    }
    cout<<dp[n]<<endl;
    return 0 ;
}