题解 [ABC369F] Gather Coins

cjh20090318 · 2024-09-02 10:51:45 · 题解

树状数组优化 DP 模板题。

题意

有 N 枚硬币，第 i 枚硬币的位置在 (R_i,C_i)。

你每次可以向右或向下移动一格，求从 (1,1) 到 (H,W) 最多能拾取多少枚硬币，并给出任意一种可行的移动方案。

分析

将所有硬币按照 R_i 为第一关键字，C_i 为第二关键字升序排列。

先考虑设一个朴素 DP，f_i 表示前 i 枚硬币且拾取第 i 枚硬币能获得的最大硬币数量。

最终答案即为 \max\limits_{i = 1}^N f_i。

这个东西很显然可以用树状数组或者线段树优化，在转移的时候记录一下每个硬币是从哪个硬币转移而来。

为了方便实现分别在开头和结尾添加 (1,1) 和 (H,W)，时间复杂度 O(N \log N)。

代码

//the code is from chenjh
#include<cstdio>
#include<algorithm>
#include<string>
#include<utility>
#define MAXN 200002
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
using ci=const int;
int h,w,n;
PII a[MAXN];
int p[MAXN];
template<typename T>
struct fenwick_tree{
    public:
        fenwick_tree(int _SIZE=0):SIZE(_SIZE){dt=new T[SIZE+1]();for(int i=0;i<=SIZE;i++)dt[i]=T(0,0);}
        ~fenwick_tree(){delete[] dt;}
        void add(int x,const T&v){for(;x<=SIZE;x+=x&-x)dt[x]=max(dt[x],v);}
        T sum(int x)const{T ret(0,0);for(;x;x^=x&-x)ret=max(ret,dt[x]);return ret;}
    private:
        T*dt;
        int SIZE;
};
int main(){
    scanf("%d%d%d",&h,&w,&n);
    fenwick_tree<PII> T(w);
    a[0]=PII(1,1),a[++n]=PII(h,w);
    for(int i=1;i<n;i++) scanf("%d%d",&a[i].x,&a[i].y);
    sort(a+1,a+n);
    for(int i=1;i<=n;i++){
        PII r=T.sum(a[i].y);//查询前缀。
        p[i]=r.second;
        T.add(a[i].y,PII(r.first+1,i));//更新单点。
    }
    printf("%d\n",T.sum(w).first-1);//最后一个硬币 (H,W) 是人为添加的，所以需要减去最后一个的贡献。
    string ans="";
    for(int i=n,t;i;i=p[i]){//一直跳上一个点，逆序构造。
        t=p[i];
        for(int _=a[i].x-a[t].x;_--;)ans+='D';
        for(int _=a[i].y-a[t].y;_--;)ans+='R';
    }
    reverse(ans.begin(),ans.end());
    puts(ans.c_str());
    return 0;
}