股票买卖 II

CI_is_safe · 2023-02-12 18:33:46 · 个人记录

原题

DP

令 f[i][0/1] 表示前 i 个股票做完买卖后当前持有 0/1 个股票的答案，然后考虑当前局面的买/卖/什么都不做。

#include<cstdio>
#include<algorithm>
using namespace std;
#define L(i,a,b) for(int i=a;i<=b;++i)
#define in scanf
const int N=100010;
int n,a[N],f[N][2];
int main(){
    scanf("%d",&n);
    L(i,1,n)in("%d",a+i);
    f[1][0]=0,f[1][1]=-a[1];
    L(i,2,n){
        f[i][0]=max(f[i-1][0],f[i-1][1]+a[i]);
        f[i][1]=max(f[i-1][0]-a[i],f[i-1][1]);
    }
    printf("%d",f[n][0]);
    return 0;
}

贪心

考虑对于每个间隔天数 >1 的股票买卖操作，都可以拆解成这些天数之间都进行操作。而如果每次操作间隔天数为 1，那么这些操作是独立的。操作即为 p_i-p_{i-1}，不操作是 0，所有相加，二者每次取较大即可。

#include<cstdio>
#include<algorithm>
using namespace std;
#define L(i,a,b) for(int i=a;i<=b;++i)
#define in scanf
const int N=100010;
int n,a[N],res;
int main(){
    scanf("%d",&n);
    L(i,1,n)in("%d",a+i);
    L(i,2,n)res+=max(0,a[i]-a[i-1]);
    printf("%d",res);
    return 0;
}