P1941 [NOIP 2014 提高组] 飞扬的小鸟 C++题解

· · 题解

分析

我们可以用 dp_{i,j} 来表示到横坐标为 i，纵坐标为 j 的最小点击屏幕的次数。依据题意，每次纵坐标可能会上升 x 或下降 y，横坐标每次可能不变或增加 1。那就有四种情况：

  1. 从 dp_{i,j-x_i} 转移到 dp_{i,j}；

  2. 从 dp_{i-1,j-x_i} 转移到 dp_{i,j}；

  3. 从 dp_{i,j+y_i} 转移到 dp_{i,j}；

  4. 从 dp_{i-1,j+y_i} 转移到 dp_{i,j}。

那么我们可以发现内存为 1 \times 10^4 \times 2 \times 10^3=2 \times 10^7，有点卡内存，可以发现每次的 dp_{i,j} 中我们使用到的只有 i 和 i-1，所以第一维可以压成 i \bmod 2（即 C++ 中的 i&1)。

对于管道的坐标，我们可以用类型为 pair<int,int> 的 p 数组代替。p 数组第一位表示下边沿高度，第二位表示上边沿高度。

判断无解可以按以下步骤进行：

我们用 cnt 来记录已通过的管道缝隙数量（一开始，cnt 为 0）。

当 p_i 没有被记录过时，枚举每个 j(0 \le j \le m)，如果说 j 不在上边沿也不在下边沿，说明撞到了管道，将 dp_{i \bmod 2,j} 赋值为 10^{18}；否则，如果说 dp_{i \bmod 2,j} 不为 10^{18} 的话，就说明有解。如果遍历完所有的 j 后，还没有找到有解的情况，说明无解，输出 0 和 cnt，并结束程序。

最后，遍历所有的 i(0 \le i \le m)，答案即为 \min\{dp_{n \bmod 2,i}\}。

代码

请勿抄袭。

本题坑点：

  1. 数组第二维要开到 2 \times 10^3，不然第 13 个测试点会 RE 或者 WA。

  2. 数组初始值一定要设大一点，如果设 10^{12} 就会在第 2 个测试点 WA。

Code:

#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> PII;
const int MAXN=2e4+10,MAXM=2e3+10;
int x[MAXN],y[MAXN],dp[2][MAXM];
PII p[MAXN];
signed main(){
    int n,m,k;
    scanf("%lld %lld %lld",&n,&m,&k);
    for(int i=1;i<=n;i++){
        scanf("%lld %lld",&x[i],&y[i]);
    }
    for(int i=1;i<=k;i++){
        int a,b,c;
        scanf("%lld %lld %lld",&a,&b,&c);
        p[a]={b,c}; 
    }
    int cnt=0;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=m;j++) dp[i&1][j]=1e18; 
        for(int j=x[i]+1;j<=x[i]+m;j++) dp[i&1][j]=min(dp[!(i&1)][j-x[i]],dp[i&1][j-x[i]])+1;
        for(int j=m+1;j<=x[i]+m;j++) dp[i&1][m]=min(dp[i&1][m],dp[i&1][j]);
        for(int j=1;j<=m-y[i];j++){
            dp[i&1][j]=min(dp[i&1][j],dp[!(i&1)][j+y[i]]);
        }
        if (p[i]!=(PII){0,0}){
            bool flag=false;
            for(int j=0;j<=m;j++){
                if (j<=p[i].first||j>=p[i].second) dp[i&1][j]=1e18;
                else if (dp[i&1][j]!=1e18) flag=true;
            }
            if (!flag) return puts("0"),printf("%lld\n",cnt)&0;
            cnt++;
        }
    }
    puts("1");
    int ans=1e18;
    for(int i=0;i<=m;i++) ans=min(ans,dp[n&1][i]);
    printf("%lld\n",ans);
    return 0;
}

代码时间复杂度为 O(n \times m)。

The End.