Java(javac 1.8) 解法, 执行用时: 477ms, 内存消耗: 46928K, 提交时间: 2021-03-06 14:47:42
import java.io.*;
import java.lang.reflect.Type;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.RoundingMode;
import java.text.DecimalFormat;
import java.util.*;
import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.Future;
import java.util.concurrent.FutureTask;
import java.util.concurrent.locks.LockSupport;
public class Main {
static class Task {
public static String roundS(double result, int scale) {
String fmt = String.format("%%.%df", scale);
return String.format(fmt, result);
// DecimalFormat df = new DecimalFormat("0.000000");
// double result = Double.parseDouble(df.format(result));
}
int rt(int x) {
if (x != fa[x]) {
int to = rt(fa[x]);
// dp[x] ^= dp[fa[x]];
fa[x] = to;
return to;
}
return x;
}
void combine(int x, int y, int val) {
int rt1 = rt(x);
int rt2 = rt(y);
if (rt1 == rt2)
return;
fa[rt1] = rt2;
// dp[rt1] = dp[x] ^ dp[y] ^ val;
g--;
}
int fa[];
int g;
static int MAXN = 10000;
static Random rd = new Random(348957438574659L);
static int[] ch[], val, size, rnd, cnt;
static int len = 0, rt = 0;
// return new node, the node below s
static int rotate(int s, int d) {
// child
int x = ch[s][d ^ 1];
// give me grandson
ch[s][d ^ 1] = ch[x][d];
// child become father
ch[x][d] = s;
// update size, update new son first
update(s);
update(x);
return x;
}
static void update(int s) {
size[s] = size[ch[s][0]] + size[ch[s][1]] + cnt[s];
}
// 0 for left, 1 for right
static int cmp(int x, int num) {
if (val[x] == num)
return -1;
return num < val[x] ? 0 : 1;
}
static int insert(int s, int num) {
if (s == 0) {
s = ++len;
val[s] = num;
size[s] = 1;
rnd[s] = rd.nextInt();
cnt[s] = 1;
} else {
int d = cmp(s, num);
if (d != -1) {
ch[s][d] = insert(ch[s][d], num);
// father's random should be greater
if (rnd[s] < rnd[ch[s][d]]) {
s = rotate(s, d ^ 1);
} else {
update(s);
}
} else {
++cnt[s];
++size[s];
}
}
return s;
}
static int del(int s, int num) {
int d = cmp(s, num);
if (d != -1) {
ch[s][d] = del(ch[s][d], num);
update(s);
} else if (ch[s][0] * ch[s][1] == 0) {
if (--cnt[s] == 0) {
s = ch[s][0] + ch[s][1];
}
} else {
int k = rnd[ch[s][0]] < rnd[ch[s][1]] ? 0 : 1;
// k points to smaller random value,then bigger one up
s = rotate(s, k);
// now the node with value num become the child
ch[s][k] = del(ch[s][k], num);
update(s);
}
return s;
}
static int getKth(int s, int k) {
int lz = size[ch[s][0]];
if (k >= lz + 1 && k <= lz + cnt[s]) {
return val[s];
} else if (k <= lz) {
return getKth(ch[s][0], k);
} else {
return getKth(ch[s][1], k - lz - cnt[s]);
}
}
static int getRank(int s, int value) {
if (s == 0)
return 1;
if (value == val[s])
return size[ch[s][0]] + 1;
if (value < val[s])
return getRank(ch[s][0], value);
return getRank(ch[s][1], value) + size[ch[s][0]] + cnt[s];
}
static int getPre(int data) {
int ans = -1;
int p = rt;
while (p > 0) {
if (data > val[p]) {
if (ans == -1 || val[p] > val[ans])
ans = p;
p = ch[p][1];
} else
p = ch[p][0];
}
return ans != -1 ? val[ans] : (-2147483647);
}
static int getNext(int data) {
int ans = -1;
int p = rt;
while (p > 0) {
if (data < val[p]) {
if (ans == -1 || val[p] < val[ans])
ans = p;
p = ch[p][0];
} else
p = ch[p][1];
}
return ans != -1 ? val[ans] : 2147483647;
}
static boolean find(int s, int num) {
while (s != 0) {
int d = cmp(s, num);
if (d == -1)
return true;
else
s = ch[s][d];
}
return false;
}
static int ans = -10000000;
static boolean findX(int s, int num) {
while (s != 0) {
if (val[s] <= num) {
ans = num;
}
int d = cmp(s, num);
if (d == -1)
return true;
else {
s = ch[s][d];
}
}
return false;
}
long gcd(long a, long b) {
if (b == 0)
return a;
return gcd(b, a % b);
}
void linear_sort(int arr[]) {
int d = 65536;
ArrayDeque bucket[] = new ArrayDeque[d];
for (int j = 0; j < d; ++j) {
bucket[j] = new ArrayDeque();
}
for (int u : arr) {
bucket[u % d].offer(u);
}
int pos = 0;
for (int j = 0; j < d; ++j) {
while (bucket[j].size() > 0) {
arr[pos++] = (int)bucket[j].pollFirst();
}
}
for (int u : arr) {
bucket[u / d].offer(u);
}
pos = 0;
for (int j = 0; j < d; ++j) {
while (bucket[j].size() > 0) {
arr[pos++] = (int)bucket[j].pollFirst();
}
}
}
int cur = 0;
int h[];
int to[];
int ne[];
void add(int u, int v) {
to[cur] = v;
ne[cur] = h[u];
h[u] = cur++;
}
public boolean dfs(String cur, HashMap<String, Integer> vis, Map<String, List<String>> list, int cl) {
vis.put(cur, cl);
for (String hp : list.get(cur)) {
if (vis.containsKey(hp)) {
if (vis.get(hp) == cl) {
return false;
}
} else {
if (!dfs(hp, vis, list, 1 - cl)) {
return false;
}
}
}
return true;
}
public class MultiSet {
TreeMap<Integer, Integer> map;
int ct = 0;
MultiSet() {
map = new TreeMap<>();
}
public void remove(int key) {
if (map.containsKey(key)) {
int times = map.get(key);
if (times == 1) {
map.remove(key);
} else {
map.put(key, times - 1);
}
ct--;
}
}
public void add(int key) {
map.put(key, map.getOrDefault(key, 0) + 1);
ct++;
}
public int last() {
return map.lastKey();
}
public int first() {
return map.firstKey();
}
public int size() {
return ct;
}
}
int color[], dfn[], low[], stack[];
int sccno[];
boolean iscut[];
int time = 0, top = 0;
int scc_cnt;
int dcc_cnt;
List<Integer> dcc[];
int root = 0;
// 无向图的强连通分量
void tarjanNonDirect(int u) {
low[u] = dfn[u] = ++time;
stack[top++] = u;
int child = 0;
for (int i = h[u]; i != -1; i = ne[i]) {
int v = to[i];
if (dfn[v] == 0) {
tarjanNonDirect(v);
low[u] = Math.min(low[u], low[v]);
if (low[v] >= dfn[u]) {
if (u != root || ++child > 1) { // 不是root，直接记为cut，是root，判断是否有两个儿子
iscut[u] = true;
}
++dcc_cnt;
// 一个割点可能会被多个点双共享
int z = -1;
do {
z = stack[--top];
//dcc[dcc_cnt].add(z);
} while (z != v);
//dcc[dcc_cnt].add(u);
}
} else {
low[u] = Math.min(low[u], dfn[v]);
// 没有特判是否直接指向父亲
// 回边，使用dfn【v】更新low【u】,因为可能是指向父亲，而父亲的low可能比较小
}
}
}
long dp11[][];
public long s(int l, int r, int a[]) {
if (l > r)
return 0;
if (dp11[l][r] != 0) {
return dp11[l][r];
}
if (l == r) {
return dp11[l][r] = a[l];
}
return dp11[l][r] = Math.max((long)a[l] - s(l + 1, r, a), (long)a[r] - s(l, r - 1, a));
}
long dp[][];
long a[];
long y(int j,int x){
return dp[j][x-1] + sa[j];
}
long x(int j){
return a[j];
}
long k(int j){
return s[j];
}
long xj(long x1,long y1,long x2,long y2,long x3,long y3){
return (x1-x2)*(y2-y3)-(y1-y2)*(x2-x3);
}
boolean bj(long x1,long y1, long x2 ,long y2, long k){
return (y1-y2) <= (x1-x2)*k;
}
long s[];
long f = 1;
long sa[];
public void solve(int testNumber, InputReader in, PrintWriter out) {
int fk = 1;int n;
int q[] = new int[500010];
int k =-1;
while(fk-->0) {
try {
n = in.nextInt();
}catch (Exception e){
break;
}
s = new long[n + 2];
long d[] = new long[n + 1];
a = new long[n+2];
sa = new long[n+2];
for (int i = 1; i <= n; ++i) {
a[i] = in.nextLong();
d[i] = in.nextLong();
}
for(int i=2;i<=n+1;++i){
s[i] = s[i-1] + d[i-1];
sa[i] = a[i]*s[i];
sa[i] += sa[i-1];
a[i] += a[i-1];
}
dp = new long[n + 2][4];
for(int x=1;x<=3;++x) {
int st = 0;
int e = 0;
q[e++] = 0;
for (int i = 1; i <= n+1; ++i) {
// dp[i][x] = dp[j][x-1] + (s[i] * (a[i] - a[j]) ) - (sa[i] - sa[j]);
// y = dp[j][x-1] + sa[j]
// x = a[j];
// k = s[i];
// dp[i] = dp[j] + (s[i]-s[j]) - a[j+1]*(i-j);
// y = dp[j] - s[j] + a[j+1]*j;
// x = a[j+1];
// k = i;
// dp[i] = dp[j] + b*(s[i] - s[j]) + c + a*(s[i]2 - 2*s[i]*s[j] + s[j]2);
// y = dp[j] + a*s[j]*s[j] - b*s[j]
// x = s[j];
// k = 2*a*s[i]
while (st + 1 < e && bj(x(q[st + 1]), y(q[st + 1],x), x(q[st]), y(q[st],x), k(i))) st++;
dp[i][x] = dp[q[st]][x-1] + (s[i] * (a[i] - a[q[st]]) ) - (sa[i] - sa[q[st]]);
// if (i + 1 - k >= k) {
while (st + 1 < e && xj(x(i), y(i ,x), x(q[e - 1]), y(q[e - 1],x), x(q[e - 2]), y(q[e - 2],x)) >= 0)
e--;
//
// dp[i] = dp[j] + c[i] + (s[i] - s[j])*x[i] - (px[i] - px[j])
// dp[j] + px[j] = s[j]*x[i] + dp[i] - c[i] + px[i] - x[i]*s[i];
// dp[i] = t[i]*(c[i] - c[0]) + s * (c[n-1] -c[0]);
// for(int j=0;j<i;++j){
// dp[i] = Math.min(dp[i] , dp[j] + c[i]2 + c[j]2 - 2c[i]*c[j] + s))
// dp[j] + c[j]2 = dp[i] -c[i]2 + 2*c[i] * c[j] -s;
// dp[i] = Math.min(dp[i] , dp[j] + (c[i]-c[j])*(t[i]) + s *(c[n-1] - c[j]));
//
// }
// dp[i] = dp[q[st]] + (c[i] - c[q[st]] + s);
//
// while(st<e && dp[q[e-1]] - c[q[e-1]] >= dp[i] - c[i]) e--;
//
// q[e++] = i;
// while (st + 1 < e && (dp[q[st + 1]] + px[q[st+1]] - dp[q[st]] - px[q[st]]) <= (s[q[st + 1]] - s[q[st]]) * (x[i])) st++;
//
// dp[i] = dp[q[st]] + c[i] + (s[i] - s[q[st]])*x[i] - (px[i] - px[q[st]]);
// while (st + 1 < e && (s[i] - s[q[e - 1]]) * (dp[q[e - 1]] + px[q[e-1]] - dp[q[e - 2]] - px[q[e-2]]) - (dp[i] + px[i] - dp[q[e - 1]] - px[q[e-1]]) * (s[q[e - 1]] - s[q[e - 2]]) >= 0)
// e--;
if(x>=2) {
q[e++] = i;
}
// }
}
}
out.println(dp[n+1][3]);
}
}
static long mul(long a, long b, long p) {
long res = 0, base = a;
while (b > 0) {
if ((b & 1L) > 0)
res = (res + base) % p;
base = (base + base) % p;
b >>= 1;
}
return res;
}
static long mod_pow(long k, long n, long p) {
long res = 1L;
long temp = k % p;
while (n != 0L) {
if ((n & 1L) == 1L) {
res = mul(res, temp, p);
}
temp = mul(temp, temp, p);
n = n >> 1L;
}
return res % p;
}
public static double roundD(double result, int scale) {
BigDecimal bg = new BigDecimal(result).setScale(scale, RoundingMode.UP);
return bg.doubleValue();
}
}
private static void solve() {
InputStream inputStream = System.in;
// InputStream inputStream = null;
// try {
// inputStream = new FileInputStream(new File("D:\\chrome_download\\exp.out"));
// } catch (FileNotFoundException e) {
// e.printStackTrace();
// }
OutputStream outputStream = System.out;
// OutputStream outputStream = null;
// File f = new File("D:\\chrome_download\\");
// try {
// f.createNewFile();
// } catch (IOException e) {
// e.printStackTrace();
// }
// try {
// outputStream = new FileOutputStream(f);
// } catch (FileNotFoundException e) {
// e.printStackTrace();
// }
InputReader in = new InputReader(inputStream);
PrintWriter out = new PrintWriter(outputStream);
Task task = new Task();
task.solve(1, in, out);
out.close();
}
public static void main(String[] args) {
new Thread(null, () -> solve(), "1", (1 << 20)).start();
// solve();
}
static class InputReader {
public BufferedReader reader;
public StringTokenizer tokenizer;
public InputReader(InputStream stream) {
reader = new BufferedReader(new InputStreamReader(stream), 32768);
tokenizer = null;
}
public String nextLine() {
String line = null;
try {
line = reader.readLine();
} catch (IOException e) {
throw new RuntimeException(e);
}
return line;
}
public String next() {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(reader.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
public char nextChar() {
return next().charAt(0);
}
public int[] nextArray(int n) {
int res[] = new int[n];
for (int i = 0; i < n; ++i) {
res[i] = nextInt();
}
return res;
}
public long nextLong() {
return Long.parseLong(next());
}
public double nextDouble() {
return Double.parseDouble(next());
}
}
}
C++(g++ 7.5.0) 解法, 执行用时: 46ms, 内存消耗: 8260K, 提交时间: 2023-05-19 16:41:13
#include<bits/stdc++.h>
using namespace std;
const int N=2e5;
const int M=5e5;
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
int n;
int l,r,pre,que[N+5];
long long x[N+5],sumw[N+5],sumx[N+5];
long long dp[N+5][2];
double slope(int x,int y){
long long v=(dp[y][1]+sumx[y])-(dp[x][1]+sumx[x]);
if(sumw[x]==sumw[y])return v>0?INF:-INF;
return 1.0*v/(sumw[y]-sumw[x]);
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
int X,Y;cin>>X>>Y;
x[i]=x[i-1]+pre;pre=Y;
sumw[i]=sumw[i-1]+X;
sumx[i]=sumx[i-1]+1LL*X*x[i];
}
x[n+1]=x[n]+pre;
sumw[n+1]=sumw[n];
sumx[n+1]=sumx[n];
++n;
l=r=1;
long long ans=1e18;
for(int i=1;i<=n;i++){
dp[i][1]=x[i]*sumw[i]-sumx[i];
while(l<r && slope(que[l],que[l+1])<1.0*x[i])l++;
if(i>1){
int j=que[l];
dp[i][2]=dp[j][1]+x[i]*(sumw[i]-sumw[j])-(sumx[i]-sumx[j]);
ans=min(ans,dp[i][2]+x[n]*(sumw[n]-sumw[i])-(sumx[n]-sumx[i]));
//cout<<i<<" "<<j<<" "<<dp[i][2]<<"\n";
}
while(l<r && slope(que[r-1],i)<slope(que[r-1],que[r]))r--;
que[++r]=i;
}
cout<<ans;
return 0;
}
C++(clang++11) 解法, 执行用时: 53ms, 内存消耗: 8184K, 提交时间: 2020-10-22 10:08:47
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
int n,w[maxn],d[maxn],head,tail,line[maxn];
long long s1[maxn],s2[maxn],c[maxn],f[maxn],ans=2e18;
double getk(int a,int b){return double(s1[a]*s2[a]-s1[b]*s2[b])/double(s1[a]-s1[b]);}
inline long long all(int a,int b){return c[b]-c[a]-s1[a]*(s2[b]-s2[a]);}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){scanf("%d%d",&w[i],&d[i]);}
n++;
for(int i=1;i<n;i++){s1[i]=s1[i-1]+w[i];}
for(int i=1;i<n;i++){s2[i+1]=s2[i]+d[i];}
for(int i=1;i<=n;i++){c[i]=c[i-1]+s1[i-1]*d[i-1];}
head=tail=1;
for(int i=1;i<n;i++){
while(head<tail&&getk(line[head+1],line[head])<s2[i]){head++;}
f[i]=c[line[head]]+all(line[head],i)+all(i,n);
while(head<tail&&getk(line[tail-1],i)>getk(line[tail],i))tail--;
line[++tail]=i;
}
for(int i=2;i<n;i++){ans=min(ans,f[i]);}
printf("%lld\n",ans);
return 0;
}
标号。
和
。分别表示第i棵树的重量（公斤为单位）和第i棵树和第i+1棵树之间的距离。最后一个数
，表示第n棵树到山脚的锯木厂的距离。
