链接:https://codeforces.com/contest/1787/problem/C
题意:给定数组a数n和s,再由\(x_i+y_i=a_i\)且\((x_i-s) \cdot (y_i-s) \geq 0\)一个式子令其值最小 $ F = a_1 \cdot x_2+y_2 \cdot x_3+y_3 \cdot x_4 + \ldots + y_{n - 2} \cdot x_{n-1}+y_{n-1} \cdot a_n $,
其中n,s<=2e5,a[i]<=2e5.
观察发现 \(F = a_1 \cdot (x_2+y_2) \cdot (x_3+y_3) \cdot x_4 + \ldots + y_{n - 2} \cdot (x_{n-1}+y_{n-1}) \cdot a_n\),s对每个xi,yi的作用是将其限制在一个值域中,容易求得上下界。发现对于每个a[i]=x[i]+y[i],设左数l右数r,若l==r,如何拆分无所谓;l<r,x[i]=max,y[i]=min;l>r,x[i]=min,y[i]=max;故可知每个x[i]只有两种取值,故dp即可。
代码:
#define int long long
using namespace std;
template <typename T> void read(T &t) {
t=0; char ch=getchar(); int f=1;
while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
do { (t*=10)+=ch-'0'; ch=getchar(); } while ('0'<=ch&&ch<='9'); t*=f;
}
template <typename T> void write(T t) {
if (t<0) { putchar('-'); write(-t); return; }
if (t>9) write(t/10);
putchar('0'+t%10);
}
int a[200100],mx[200100],mi[200100],f[200100][3];
void solve(){
int n,s;cin>>n>>s;
for(int i=1;i<=n;i++) read(a[i]);
for(int i=2;i<=n-1;i++){
if(s>a[i]){
mi[i]=0,mx[i]=a[i];
continue;
}
int minx=a[i]-s,maxx=s;
int u=min(minx,maxx),v=max(minx,maxx);
mi[i]=u,mx[i]=v;
}
mi[1]=mx[1]=a[1],mi[n]=mx[n]=a[n];
int ans=0;
for(int i=1;i<=n;i++){
f[i][1]=min(f[i-1][0]+mx[i-1]*mx[i],f[i-1][1]+mi[i-1]*mx[i]);
f[i][0]=min(f[i-1][0]+mx[i-1]*mi[i],f[i-1][1]+mi[i-1]*mi[i]);
}
ans=min(f[n][0],f[n][1]);
cout<<ans<<endl;
}
signed main(){
int T;read(T);
while(T--) solve();
}
标签:TypeDB,ch,cdot,200100,mi,Remove,int,Bracket,mx
From: https://www.cnblogs.com/wjhqwq/p/17077603.html