cfgym100253K

201708 （ACM）动态规划

题意

• 有n台机器，第i台必须在第d[i]天之前修好。
• 修理机一直往下标递增或者递减的方向移动，遇到已经修好的机器或者边界就停止。
• 问至少需要多少台修理机。

题解

• dp，d[i]=d[j]+1。
• 记录路径。
• 双指针预处理每个点往左边最多能到哪里。

代码

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define sz(a) (int)a.size()
#define rep(i, a, b) for(int i=(a); i<(b); i++)
#define de(a) cout<<#a<<" = "<<a<<endl
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
//----
const int N=300005;
int n;
int a[N],lm[N],mr[N],dp[N],pre[N],ty[N];
void init() {
    for(int l=1,r=1,t=1;r<=n;++r,++t) {
        while(a[r]<t) {
            ++l;
            --t;
        }
        lm[r]=l;
    }
    for(int l=n,r=n,t=1;l;--l,++t) {
        while(a[l]<t) {
            mr[r]=l+1;
            --r;
            --t;
        }
    }
    rep(i,1,n+1) if(!mr[i]) mr[i]=1;
}
int main(){
    scanf("%d",&n);
    rep(i,1,n+1) scanf("%d",a+i);
    init();
    rep(i,1,n+1) {
        pre[i]=lm[i];
        ty[i]=0;
        if(mr[i]<pre[i]) {
            pre[i]=mr[i];
            ty[i]=1;
        }
        dp[i]=dp[pre[i]-1]+1;
    }
    printf("%d\n",dp[n]);
    vector<pii> ans;
    int now=n;
    for(;pre[now]&&now;) {
        int x=pre[now],y=now;
        if(ty[now]) swap(x,y);
        ans.pb(mp(x,y));
        now=pre[now]-1;
    }
    for(int i=sz(ans)-1;i>=0;--i) printf("%d %d\n",ans[i].fi,ans[i].se);
    return 0;
}