「NOIP2014」飞扬的小鸟
2024-09-06 07:35:31
传送门
Luogu
解题思路
考虑 \(\text{DP}\)
设 \(dp[i][j]\) 表示飞到 \((i, j)\) 这个点的最小触屏次数。
转移其实比较显然,但问题是每次上升时都可以点很多次,这一维次数如果枚举的话,就会带来复杂度的GG。
我们考虑到一个性质,这个无限次点每次都是增加固定的高度,有点像完全背包,于是我们就可以用完全背包的思想来优化,转移时也可以从当前这一列的下方转移。
还有就是如何判断解的情况。
我们从终点向起点枚举,取第一个可以被走到的列就好了。
细节注意事项
- 咕咕咕
参考代码
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <ctime>
#define rg register
using namespace std;
template < typename T > inline void read(T& s) {
s = 0; int f = 0; char c = getchar();
while (!isdigit(c)) f |= (c == '-'), c = getchar();
while (isdigit(c)) s = s * 10 + (c ^ 48), c = getchar();
s = f ? -s : s;
}
const int _ = 10000 + 10;
const int __ = 1000 + 10;
int n, m, k, x[_], y[_];
int tp[_], bt[_], dp[_][__];
int main() {
#ifndef ONLINE_JUDGE
freopen("in.in", "r", stdin);
#endif
read(n), read(m), read(k);
for (rg int i = 0; i < n; ++i) read(x[i]), read(y[i]);
for (rg int i = 1; i <= n; ++i) bt[i] = 0, tp[i] = m + 1;
for (rg int a, i = 1; i <= k; ++i) read(a), read(bt[a]), read(tp[a]);
memset(dp, 0x3f, sizeof dp);
for (rg int i = 1; i <= m; ++i) dp[0][i] = 0;
for (rg int i = 1; i <= n; ++i) {
for (rg int j = 1; j <= m; ++j) {
if (j >= x[i - 1]) {
dp[i][j] = min(dp[i][j], dp[i - 1][j - x[i - 1]] + 1);
dp[i][j] = min(dp[i][j], dp[i][j - x[i - 1]] + 1);
}
if (j == m) {
for (rg int k = j - x[i - 1]; k <= m; ++k) {
dp[i][j] = min(dp[i][j], dp[i - 1][k] + 1);
dp[i][j] = min(dp[i][j], dp[i][k] + 1);
}
}
}
for (rg int j = bt[i] + 1; j <= tp[i] - 1; ++j)
if (j + y[i - 1] <= m) dp[i][j] = min(dp[i][j], dp[i - 1][j + y[i - 1]]);
for (rg int j = tp[i]; j <= m; ++j) dp[i][j] = 0x3f3f3f3f;
for (rg int j = bt[i]; j >= 1; --j) dp[i][j] = 0x3f3f3f3f;
}
int cnt = k, ans = 0x3f3f3f3f;
for (rg int i = n; i >= 1; --i) {
for (rg int j = bt[i] + 1; j <= tp[i] - 1; ++j)
ans = min(ans, dp[i][j]);
if (ans < 0x3f3f3f3f) break; if (tp[i] <= m) --cnt;
}
if (cnt == k) printf("1\n%d\n", ans);
else printf("0\n%d\n", cnt);
return 0;
}
完结撒花 \(qwq\)
最新文章
- java中的接口interface
- 关于tableview内cell自定义的注册以及创建
- 前端构建工具gulp介绍
- hdu 1851 尼姆+巴什博弈
- Libjingle库简介
- Sql Server来龙去脉系列之四 数据库和文件
- Java的别名机制
- 10.12_win8风格,把专业书籍当小说看,SQLite
- Linux进程的状态转换图
- 当在浏览器地址栏里输入URL后会发生什么事情
- code force 403C.C. Andryusha and Colored Balloons
- 【Unity与23种设计模式】代理模式(Proxy)
- PHP中文关键词匹配
- Redis使用单进程单线程方式的优缺点分析
- 类(字符串型;日期时间型;Math)
- laravel项目composer安装
- sublime配置 sublimecondeintel 分号后不要提示
- Error: Program type already present: okhttp3.Authenticator$1
- emoji &; click copy
- java面试第十八天
热门文章
- ENTRYPOINT与CMD/实现切换用户执行
- 解决小程序报错 Page ";pages/index/main"; has not been registered yet.
- iOS 开发中常用的排序(冒泡、选择、快速、插入、希尔、归并、基数)算法
- php类的魔术方法也就是带下划线的类方法介绍及应用
- centos610安装postgresql
- Mybatis学习day2
- MVC 拦截器
- spark实验(二)--scala安装(1)
- 导出EXCEL设置单元格格式
- ubuntu13.10安装tomcat