20018: 蚂蚁王国的越野跑

http://cs101.openjudge.cn/practice/20018/

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Fenwick
{
private:
    int n;
    vector<int> tree;

public:
    Fenwick(int n) : n(n), tree(n + 1, 0) {}

    void update(int i)
    {
        while (i <= n)
        {
            ++tree[i];
            i += (i & -i);
        }
    }

    long long query(int i)
    {
        long long s = 0;
        while (i > 0)
        {
            s += tree[i];
            i &= i - 1;
        }
        return s;
    }
};

int main()
{
    cin.tie(nullptr)->sync_with_stdio(false);

    int N;
    cin >> N;
    vector<int> v(N), vals(N);
    for (int i = 0; i < N; ++i)
    {
        int ipt;
        cin >> ipt;
        v[i] = ipt, vals[i] = ipt;
    }

    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());

    Fenwick BIT(N);

    long long ans = 0;
    for (const auto &x : vals)
    {
        int r = lower_bound(v.begin(), v.end(), x) - v.begin() + 1;
        ans += BIT.query(r - 1);
        BIT.update(r);
    }

    cout << ans << '\n';
    return 0;
}

M20744: 土豪购物

dp, greedy, http://cs101.openjudge.cn/pctbook/M20744/

思路：很标准的dp题目，把两种可能的情况都考虑进取就行，练习从底向上的dp写法

#include<vector>
#include<stdio.h>
using namespace std;
int max(int a,int b){
    return(a>b)?a:b;
}
int min(int a,int b){
    return(a<b)?a:b;
}
int main(){
    int p,q;
    q=1;
    char s=',';
    vector<int> w;
    while(q!=-1){
        scanf("%d",&p);
        w.push_back(p);
        q=scanf("%c",&s);//最后会读到一个换行
    }
    int n=w.size();
    vector<pair<int,int>>dp(n,{-100000,-100000});
    dp[n-1].first=w[n-1];
    dp[n-3].second=w[n-1]+w[n-3];
    for(int i=n-2;i>=0;i--){
        dp[i].first=max(w[i],dp[i+1].first+w[i]);
        if(i<n-3){        dp[i].second=max(dp[i+2].first,dp[i+1].second)+w[i];
        }
    }
    int ans=-100000;
    for(int i=0;i<n;i++){
        ans=max(ans,max(dp[i].first,dp[i].second));
    }
    printf("%d",ans);
    return 0;
}