0 分求助
查看原帖
0 分求助
1086853
txp2024楼主2024/6/15 16:13

2个样例都过了。但是交上去全WA。下载测试点后本地测试和正确答案一模一样。但是就是不过,求解答。

//P1941 [NOIP2014 提高组] 飞扬的小鸟
//我的代码
#include <vector>
#include <stdio.h>
#include <algorithm>
#include <stdlib.h>
#include <math.h>

// #define __LONG_MAX__ 0x7fffffffL

typedef long long ll;

struct operate
{
    ll up; //点击一下上升的高度
    ll down; //不点击下降的高度
};

struct _data //管道数据
{
    ll x; //横坐标
    ll up; //管道上限
    ll down; //管道下限

    //运算符重载控制sort函数
    bool operator <(const _data &other)const{
        return x < other.x;
    }
};


std::vector< std::vector< ll > > dp(2); //动态规划数组
std::vector< operate > opers; //储存操作数据
std::vector< _data > datas; //储存障碍数据
std::vector< bool > out; //储存小年可以通过几个障碍
ll n, m, k, ans = __LONG_LONG_MAX__, maxout = 0; //界面的长度,高度和水管的数量

int main()
{
    freopen("D:\\code\\SHU_RU.in", "r", stdin);
    //freopen("D:\\SHU_CHU.out", "w", stdout);
    scanf("%lld%lld%lld", &n, &m, &k);
    
    //输入操作数据
    opers.resize(n);
    for (ll i = 0; i < n; i++)
    {
        scanf("%lld%lld", &opers[i].up, &opers[i].down);
    }
    
    //输入管道数据
    datas.resize(k);
    for (ll i = 0; i < k; i++)
    {
        scanf("%lld%lld%lld", &datas[i].x, &datas[i].down, &datas[i].up);
    }
    std::sort(datas.begin(), datas.end());
    
    //动态规划
    dp[0].resize(m, 0);
    dp[1].resize(m, __LONG_MAX__);
    for (ll i = 1; i <= n; i++)
    {
        //上升
        for (ll j = opers[i-1].up; j < m; j++)
        {
            dp[i%2][j] = std::min(dp[i%2^1][j-opers[i-1].up]+1, dp[i%2][j-opers[i-1].up]+1);
        }

        //碰到天花板的特殊情况
        for (ll j = m; j < m+opers[i-1].up; j++)
        {
            dp[i%2][m-1] = std::min(dp[i%2^1][j-opers[i-1].up]+1, dp[i%2][m-1]);
        }

        //往下掉
        for (ll j = 0; j <= m-opers[i-1].down-1; j++)
        {
            dp[i%2][j] = std::min(dp[i%2][j], dp[i%2^1][j+opers[i-1].down]);
        }
        
        //处理因为管道而无法到达的地方
        if (datas.size() && datas.front().x == i)
        {
            //下限处理
            for (ll j = 0; j < datas.front().down; j++)
            {
                dp[i%2][j] = __LONG_MAX__;
            }

            //上线处理
            for (ll j = m-1; j >= datas.front().up-1; j--)
            {
                dp[i%2][j] = __LONG_MAX__;
            }
            
            //弹出
            datas.erase(datas.begin());
            for (ll j = 0; j < m; j++)
            {
                if (dp[i%2][j] < __LONG_MAX__)
                {
                    maxout++;
                    break;
                }
                
            }
            
        }

        //预处理
        dp[i%2^1].resize(0);
        dp[i%2^1].resize(m, __LONG_MAX__);
    }

    //寻找结果
    for (ll i = 0; i < m; i++)
    {
        ans = std::min(ans, dp[n%2][i]);
    }

    //输出结果
    switch (ans)
    {
    case __LONG_MAX__:
        printf("0\n%lld\n", maxout);
        break;
    
    default:
        printf("1\n%lld\n", ans);
        break;
    }
    return 0;
}

下载下来的测试点 输入: 5 5 0 3 3 2 1 2 3 2 1 3 2

输出: 1 2

我的输出: 1 2

vscode 输入输出截图

2024/6/15 16:13
加载中...