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
