Luogu

分析

设 $dp_{i,j}$ 表示飞到 $(i,j)$ 的最少点击次数。

这样子往上飞就是完全背包,往下飞就是 01 背包。注意判一下超出 $m$ 的情况。

写起来细节感觉非常的多...反正我写了 2/3 个晚自习

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline void chkmin(int& x,int y) { if (y<x) x=y; }
inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=10000+10,M=1000+10;
const int inf=0x3f3f3f3f;

int n,m,k;
int x[N],y[N];
int l[N],h[N];
int dp[N][M<<1];

int main() {
    n=read(),m=read(),k=read();
    for (re int i=1;i<=n;++i) x[i]=read(),y[i]=read();
    for (re int i=1;i<=n;++i) l[i]=1,h[i]=m;
    for (re int i=1;i<=k;++i) {
        int p=read(); l[p]=read()+1,h[p]=read()-1;
    }
    memset(dp,0x3f,sizeof(dp));
    for (re int i=1;i<=m;++i) dp[0][i]=0;
    for (re int i=1;i<=n;++i) {
        for (re int j=1+x[i];j<=m+x[i];++j)
            chkmin(dp[i][j],min(dp[i-1][j-x[i]],dp[i][j-x[i]])+1);
        for (re int j=m+1;j<=m+x[i];++j)
            chkmin(dp[i][m],dp[i][j]);
        for (re int j=1;j<=m-y[i];++j)
            chkmin(dp[i][j],dp[i-1][j+y[i]]);
        for (re int j=1;j<l[i];++j) dp[i][j]=inf;
        for (re int j=m;j>h[i];--j) dp[i][j]=inf;
    }
    int ans=inf;
    for (re int i=1;i<=m;++i) chkmin(ans,dp[n][i]);
    if (ans<inf) printf("1\n%d\n",ans);
    else {
        int p=ans=0;
        for (re int i=1;i<=n;++i) {
            int flag=0;
            for (re int j=1;j<=m;++j)
                if (dp[i][j]!=inf) { flag=1; break; }
            if (!flag) break;
            ans+=(l[i]!=1||h[i]!=m);
        }
        printf("0\n%d\n",ans);
    }
    return 0;
}
最后修改:2019 年 10 月 21 日 09 : 05 PM