商品交易

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Scanner;

/*
 * @author Moze 2020
 * 思想是动态规划，因为直接穷举会超时。
 * 动态规划的递推式是下面这样的：
 * ①初始index=1时，只有两种：买（M[1][1]=-A[1]），或者不买M[1][0]=0
 * 同时可以得到交易次数：买（op[1][1]=1），或者不买M[1][0]=0;
 * ②接下来就是2~n-1次：设为index次
 *   又分为有还是没有，时间有限，只介绍没有，有逻辑基本类似，可以见代码
 *   有的话，要么是index-1次有，index没卖，或者index-1时没有有，但是index买了。
 *   对这两个值进行比较，然后再根据谁大，来获得op的值即可
 * ③n次时同②，只不过由于最后卖了肯定比不卖挣得多，因此，拿了出来只计算卖了的
 * 然后就直接得到结果即可
 */
public class Main {
	static int n;
	static long A[];
	//每种情况赚了多少钱:第一维度为第几个城市，第二维度为是否含有
	static long M[][];
	//每种情况至少需要多少交易次数
	static long op[][];
	public static void main(String[] args) {
		Scanner aa = new Scanner(System.in);
		n=aa.nextInt();
		A= new long[n+1];
		for(int i=1;i<=n;i++)
			A[i]=aa.nextInt();
		M = new long[n+1][2];
		op = new long[n+1][2];
		M[1][0]=0;op[1][0]=0;
		M[1][1]=-A[1];op[1][1]=1;
		for(int i=2;i<n;i++){
			//i时没有
			if(M[i-1][1]+A[i] > M[i-1][0]){
				M[i][0]=M[i-1][1]+A[i];
				op[i][0]=op[i-1][1]+1;
			}else if(M[i-1][1]+A[i] == M[i-1][0]){
				M[i][0]=M[i-1][1]+A[i];
				op[i][0]=Math.min(op[i-1][1]+1,op[i-1][0]);
			}else{
				M[i][0] =  M[i-1][0];
				op[i][0] = op[i-1][0];
			}
			//i时有
			if(M[i-1][1]>M[i-1][0]-A[i]){
				M[i][1]=M[i-1][1];
				op[i][1]=op[i-1][1];
			}else if(M[i-1][1]==M[i-1][0]-A[i]){
				M[i][1]=M[i-1][1];
				op[i][1]=Math.min(op[i-1][1], op[i-1][0]+1);
			}else{
				M[i][1]=M[i-1][0]-A[i];
				op[i][1]= op[i-1][0]+1;
			}
		}
		long max=0;
		long min_op;
		if(M[n-1][0]>M[n-1][1]+A[n]){
			max=M[n-1][0];
			min_op=op[n-1][0];
		}else if(M[n-1][0]==M[n-1][1]+A[n]){
			max=M[n-1][0];
			min_op = Math.min(op[n-1][0], op[n-1][1]+1);
		}else{
			max=M[n-1][1]+A[n];
			min_op = op[n-1][1]+1;
		}
		if(max<=0){
			System.out.println(0+" "+0);
			return ;
		}
		System.out.println(max+" "+min_op);
	}
	
	
}

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n,cnt=0;
    cin>>n;
    long a[n],s=0;
    bool d = false;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    for(int i=1;i<n;i++){
        if(a[i]>a[i-1]){
            s += a[i]-a[i-1];
            if(!d)
                cnt++;
            d = true;
        }
        if(a[i]<a[i-1]){
            cnt += d;
            d = false;
        }
    }
    cnt += d;
    cout<<s<<" "<<cnt<<endl;
    return 0;
}

import java.util.*;
import java.lang.Math;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] array = new int[n];
        for(int i = 0; i < n; i++){
            array[i] = sc.nextInt();
        }
        long[][] dp = new long[n][2];
        dp[0][0] = 0;
        dp[0][1] = -array[0];
        int n0 = 0;
        int n1 = 1;
        for (int i = 1; i < n; i++){
            if (dp[i-1][0] < array[i] + dp[i-1][1]) {
                n0 = n1 + 1;
            }
            dp[i][0] = Math.max(dp[i-1][0], array[i] + dp[i-1][1]);
            
            if (dp[i-1][1] < dp[i-1][0] - array[i]) {
                n1 = n0 + 1;
            }
            dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] - array[i]);
        }
        long res = Math.max(dp[n-1][0], dp[n-1][1]);
        if (res == dp[n-1][0]) {
            System.out.println(res + " " + n0);
        } else if (res == dp[n-1][1]) {
            System.out.println(res + " " + n1);
        }
        
    }
}

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,res1=0,res2=0;
    long long num=0;
    cin>>n;
    vector<int>a(n);
    for(int i=0;i<n;i++)
        cin>>a[i];
    for(int i=1;i<n;i++)
    {
        if (a[i] > a[i - 1]) 
        {
            num += a[i] - a[i - 1];
            res1 += res2 ^ 1;
            res2 = 1;
        } 
        else if (a[i] < a[i - 1]) {
            res1 += res2;
            res2 = 0;
        }
    }
    cout<<num<<" "<<res1+res2<<endl;
    return 0;
}

n = int(input())
num = list(map(int, input().split()))
deal = 0
profit = 0
cnt = 0
for i in range(1,n):
    if num[i] > num[i-1]:
        profit += num[i]-num[i-1]
        if deal == 0:
            cnt += 1
        deal = 1
    if num[i] < num[i-1]:
        cnt += deal
        deal = 0
print(profit,cnt+deal)

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];

        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        // 不持有宝石的收益和交易次数 
        long value0 = 0,cnt0 = 0;
        // 持有宝石的收益和交易次数 
        long value1 = -arr[0],cnt1 = 1;
        
        for (int i = 1; i < n; i++) {
            if(value0<value1+arr[i]){
                value0 = value1+arr[i];
                cnt0 = cnt1+1;
            }
            if(value1<value0-arr[i]){
                value1 = value0-arr[i];
                cnt1 = cnt0+1;
            }
        }

        long max = 0,minCnt = 0;
        for (int i = 1; i < n; i++) {
            if(value0>max){
                max = value0;
                minCnt = cnt0;
            }else if(value0==max){
                minCnt = Math.min(minCnt,cnt0);
            }
        }
        System.out.println(max+" "+minCnt);
    }
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        long[] arr = new long[n];
        for (int i = 0; i < n; i++) {
            arr[i] = in.nextLong();
        }
        fun(arr);
    }

    // 最大的收益和交易次数-无脑动态规划
    public static void fun(long[] arr) {
        int n = arr.length;
        long[][] dp = new long[n][2]; // 走到第i个国家的持有或卖出的最大收益 1持有 0卖出
        int[][] time = new int[n][2];
        dp[0][0] = 0; // base case
        dp[0][1] = -arr[0];
        time[0][0] = 0;
        time[0][1] = 1;
        for (int i = 1; i < n; i++) {
            if (dp[i-1][1] + arr[i] > dp[i-1][0]) {
                dp[i][0] = dp[i-1][1] + arr[i]; // 卖出
                time[i][0] = time[i-1][1] + 1;
            } else {
                dp[i][0] = dp[i-1][0];
                time[i][0] = time[i-1][0];
            }
            if (dp[i-1][0] - arr[i] > dp[i-1][1]) {
                dp[i][1] = dp[i-1][0] - arr[i]; // 买入
                time[i][1] = time[i-1][0] + 1;
            } else {
                dp[i][1] = dp[i-1][1];
                time[i][1] = time[i-1][1];
            }

        }
        System.out.println(dp[n-1][0] + " "+ time[n-1][0]);
    }

}