2 条题解
-
0
/* dp[i]=min(dp[i], dp[j]+st[i](sf[i]-sf[j])+s(sf[n]-sf[j]));
dp[i]=dp[j]+st[i](sf[i]-sf[j])+s(sf[n]-sf[j]));
dp[i]-st[i]sf[i]-ssf[n]= dp[j]-s*sf[j]- st[i]sf[j] dp[j]-ssf[j] =st[i]sf[j] + dp[i]-st[i]sf[i]-ssf[n] yj=dp[j]-ssf[j] xj=sf[j] k=st[i] b=dp[i]-st[i]sf[i]-ssf[n]
*/
#include <bits/stdc++.h> using namespace std; typedef long long LL; const int N=310000; LL dp[N], f[N], t[N], st[N], sf[N], s; int q[N]; double X(int j){ return 1.0*sf[j];} double Y(int j){ return 1.0*(dp[j]-s*sf[j]);} double K(int j1, int j2){return (X(j2)==X(j1))?1e18*( Y(j2)-Y(j1) ) : ( Y(j2)-Y(j1) ) / ( X(j2)-X(j1) ) ;} int main() { //freopen("a.in", "r", stdin); freopen("a.out", "w", stdout); int n; scanf("%d%lld", &n, &s); st[0]=0; sf[0]=0; for(int i=1;i<=n;i++) { scanf("%lld%lld", &t[i], &f[i]); st[i]=st[i-1]+t[i]; sf[i]=sf[i-1]+f[i]; } int l=1, r=1; q[1]=0; dp[0]=0; for(int i=1;i<=n;i++) { while(l<r && K(q[l], q[l+1]) <= st[i] ) l++; dp[i]=dp[q[l]] + st[i]*(sf[i]-sf[q[l]]) + s*(sf[n]-sf[q[l]]); while( l<r && K(q[r-1], q[r] ) >= K(q[r], i) ) r--; q[++r]=i; } printf("%lld\n", dp[n]); return 0; } -
0
/* dp[i]=min(dp[i],dp[j]+st[i]*(sf[i]-sf[j])+s*(sf[n]-sf[j])); dp[i]=dp[j]+st[i]*(sf[i]-sf[j])+s*(sf[n]-sf[j])); dp[i]-st[i]*sf[i]-s*sf[n]= dp[j]-s*sf[j]- st[i]*sf[j] dp[j]-s*sf[j] =st[i]*sf[j] + dp[i]-st[i]*sf[i]-s*sf[n] yj=dp[j]-s*sf[j] xj=sf[j] k=st[i] b=dp[i]-st[i]*sf[i]-s*sf[n] */ #include<bits/stdc++.h> using namespace std; typedef long long LL; const int N=310000; LL dp[N],f[N],t[N],st[N],sf[N],s;int q[N]; double X(int j){ return 1.0*sf[j];} double Y(int j){ return 1.0*(dp[j]-s*sf[j]);} double K(int j1,int j2){return (X(j2)==X(j1))?1e18*( Y(j2)-Y(j1) ) :( Y(j2)-Y(j1) ) / ( X(j2)-X(j1) ) ;} int main() { //freopen("a.in","r",stdin);freopen("a.out","w",stdout); int n;scanf("%d%lld",&n,&s); st[0]=0;sf[0]=0; for(int i=1;i<=n;i++) { scanf("%lld%lld",&t[i],&f[i]); st[i]=st[i-1]+t[i]; sf[i]=sf[i-1]+f[i]; } int l=1,r=1;q[1]=0;dp[0]=0; for(int i=1;i<=n;i++) { while(l<r && K(q[l],q[l+1])<=st[i] ) l++; dp[i]=dp[q[l]]+st[i]*(sf[i]-sf[q[l]])+s*(sf[n]-sf[q[l]]); while( l<r && K(q[r-1],q[r] ) >= K(q[r],i) ) r--; q[++r]=i; } printf("%lld\n",dp[n]); return 0; }
- 1
信息
- ID
- 1809
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 5
- 标签
- 递交数
- 45
- 已通过
- 17
- 上传者