BZOJ 1270: [BeijingWc2008]雷涛的小猫( dp )
2024-08-30 18:29:06
简单的dp..
dp(i,j) = max(dp(x,y))+cnt[i][j], (x,y)->(i,j)是合法路径.
设f(i)= max(dp(x,y))(1≤x≤N, 1≤y≤i), g(i,j) = max(dp(i, k))(1≤k≤j)
那么dp(i,j) = max(f(j+delta), g(i,j+1))+cnt[i][j]. 递推即可. 时间复杂度O(NH)
-----------------------------------------------------------------------
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2009;
int N, H, delta, cnt[maxn][maxn];
int dp[maxn][maxn], f[maxn], g[maxn][maxn];
void init() {
scanf("%d%d%d", &N, &H, &delta);
memset(cnt, 0, sizeof cnt);
for(int i = 0; i < N; i++) {
int t; scanf("%d", &t);
while(t--) {
int h; scanf("%d", &h);
cnt[i][h]++;
}
}
}
void work() {
f[H] = 0;
for(int i = 0; i < N; i++)
f[H] = max(f[H], dp[i][H] = g[i][H] = cnt[i][H]);
for(int h = H; --h; ) {
f[h] = f[h + 1];
for(int i = 0; i < N; i++) {
int t = g[i][h + 1];
g[i][h] = t;
if(h + delta <= H) t = max(t, f[h + delta]);
dp[i][h] = t + cnt[i][h];
f[h] = max(f[h], dp[i][h]);
g[i][h] = max(g[i][h], dp[i][h]);
}
}
int ans = 0;
for(int i = 0; i < N; i++)
ans = max(ans, dp[i][1]);
printf("%d\n", ans);
}
int main() {
init();
work();
return 0;
}
-----------------------------------------------------------------------
1270: [BeijingWc2008]雷涛的小猫
Time Limit: 50 Sec Memory Limit: 162 MB
Submit: 1004 Solved: 483
[Submit][Status][Discuss]
Description
Input
Output
Sample Input
Sample Output
8
HINT
Source
最新文章
- HDU2438 数学+三分
- C# 实现 Snowflake算法 ID生成
- js作用域的一个小例子
- java新手笔记32 jdk5新特性
- Eclipse的下载和安装
- 记一次网站服务器迁移(my)
- asp.net 错误处理
- CentOS 6.4源码编译安装httpd并启动测试
- hdu 1384 Intervals
- jQuery 查找带有某一属性的元素
- 总结微信公众平台网页开发中遇到的ios的兼容问题
- apache http添加证书转成https
- 【Vue.js】加载更多—vue-infinite-scroll
- python与RabbitMQ
- HDD ,SSD和PCIE SSD性能测试
- php laravel加密 form表单认证 laravel分页
- Reinforcement Learning: An Introduction读书笔记(1)--Introduction
- [grub2] grub2修改启动顺序
- CF891C Envy
- nfs挂载无法卸载