洛谷1052(路径压缩后简单dp)
2024-08-30 03:55:22
同POJ3744写法都是一样的。
距离太长无意义可以压缩,注意不是随便压的,想一想可以跟%T发生关系。
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
using namespace std; const int maxn = ;
int L, S, T, M, pos[], a[maxn], f[maxn]; int main() {
scanf("%d %d %d %d", &L, &S, &T, &M);
for (int i = ; i <= M; i++)
scanf("%d", &pos[i]);
sort(pos + , pos + + M);
for (int i = ; i <= M; i++) {
if (pos[i] - pos[i - ] > T) {
for (int j = M; j >= i; --j)
pos[j] -= pos[i] - pos[i - ] - T - (pos[i] - pos[i - ]) % T;
}
} for (int i = ; i <= M; i++) a[pos[i]] = ;
L = pos[M] + ;
for (int i = ; i <= L; i++) f[i] = ;
for (int i = ; i < L; i++) {
for (int j = S; j <= T; j++) {
int arrive = min(L, i + j);
f[arrive] = min(f[arrive], f[i] + a[arrive]);
}
} printf("%d\n", f[L]);
return ;
}
最新文章
- ExtJs4之Grid详细
- WCF 服务的ABC之绑定(六)
- Winform程序只允许运行一个程序实例
- 查看Eclipse版本号,及各个版本区别
- C++判断一个数字是否为质数
- RxSwift(一)
- Codeforces 798D Mike and distribution
- 使用VS2015编译grpc_1.3.1
- alfred
- SQL008存储过程总结
- 用Vue-cli生成vue+webpack的项目模板怎么设置为vue1.0版本?
- 2.2 IPython基础
- Shell记录-Shell脚本基础(六)
- webpack4.26的详细配置,包含babel, eslint, postcss, 及各种所需loader,内含大量注释
- Hadoop,MapReduce,HDFS面试题
- C#(Wpf)实现小键盘
- docker安装MySQL软件
- Oracle 查看session级别信息
- python tensorflow方法手记
- win10 如何配置 java jdk1.8环境变量(2017.8.17 )jdk1.8.0_144