洛谷 P6046 [CTSC2000]快乐的蜜月
先讲解一下如何处理这道题的毒瘤输入。\(m\) 和 \(d\) 之间的“/”和“ TO ”都可以用 getchar() 强行吃掉,日期的转换可以用公式 \(s_{m-1} + d\) 表示,其中 \(s\) 是每月日数的前缀和。
int s[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
inline int getid(int month, int day){
return s[month - 1] + day;
}
int main(){
...
if(y % 4 == 0 && (y % 100 != 0 || y % 400 == 0))
s[2] = 29;
for(int i = 1; i <= 12; ++i)
s[i] += s[i - 1];
...
}
可以用链式前向星存储预约。对于每一份从 \(i\) 日到 \(j\) 日的预约,建立一条从 \(j\) 到 \(i\) 的边。
如果是 \(k = 1\) 的特殊情况,很容易想到 \(O(r)\) 的动态规划做法:
\(\quad\bullet\) 设 \(dp_i\) 为到 \(i\) 日时的最大收入。
\(\quad\bullet\) \(dp_i = max \left\{ dp_{i - 1}, dp_j + p \cdot (i - j) \right\}\),其中 \(j\) 满足存在自 \(j\) 日到 \(i\) 日的预定。
对于 \(k \neq 1\) 的情况,可以二维 dp。即:
\(\quad\bullet\) \(dp_i\) 是一个大小为 \(k\) 的有序集合,从 \(dp_{i,1}\) 至 \(dp_{i,k}\) 分别表示到 \(i\) 日的前 \(k\) 大收入。
\(\quad\bullet\) \(dp_i = dp_{i - 1} \cup dp ^ \prime _ j\),其中 \(j\) 满足存在自 \(j\) 日到 \(i\) 日的预定,对于\(dp ^ \prime _ j\) 中的每一个元素 \(dp ^ \prime_{j, a}\),有 \(dp ^ \prime_{j, a} = dp_{j, a} + p \cdot (i - j)\)。
显然,所谓的“有序集合”可以用数组模拟,两个有序数列的合并操作可以归并排序。
void merge(int *dest, int *src1, int *src2){
for(int i = 0; i < k; ++i)
*(dest++) = *src1 > *src2 ? *(src1++) : *(src2++);
}
收入为 \(0\) 也是一种可能,不可以在 \(dp_{s_{12}, k} = 0\) 时直接输出 \(-1\)。正确做法如下:
if(dp[s[12]][k - 1] == 0)
std::printf("-1\n");
else
std::printf("%d\n", dp[s[12]][k]);
时间复杂度 \(O(k \cdot r)\)。
最新文章
- linux java so 历险
- BZOJ1845 : [Cqoi2005] 三角形面积并
- js的with语句使用方法
- IOS-day01_OC中类的创建以及使用
- PHP学习笔记(2) - 对PHP的印象
- JS日期时间格式化
- 用PyRestful快速构建Tornado下REST APIs 的支持
- 我的Python成长之路---第一天---Python基础(1)---2015年12月26日(雾霾)
- Shell错误[: missing `]&#39;
- 初识golang
- Codeforces Round #383 (Div. 2)C. Arpa&#39;s loud Owf and Mehrdad&#39;s evil plan
- Go 语言变量
- “妄”眼欲穿之CSS 居中问题
- ELK 安装与基本配置(一)
- linux安装flash player来播放视频
- Seaborn图形可视化库
- 1.5sleep()方法
- __init__函数
- 转载:CSS3图标图形生成技术个人攻略
- js 删除数组的某一项或者几项的方法