[BJWC2008]雷涛的小猫
2024-10-16 17:59:58
dp。
刚开始我想的是dp[i][j]表示在第 i 棵树上,高度为h能吃到的最多的果子,如此能得到转移方程: dp[i][j] = max(dp[i][j + 1], dp[k][j + derta]) (k = 1~n && k != i)。但因为这样写会导致dp[k][j + derta] (k > i)的部分没有更新,所以应该把dp试的两胃交换一下。这样dp方程就能正常转移了:
dp[i][j] = max(dp[i + 1][j], max(dp[i + derta][k]) (k = 1~n && k != j) )
然而这样的时间复杂度是O(h * n * n)的,过不了。
优化:观察 max(dp[i + derta][k]) (k = 1~n && k != j),实际上我们就是在高度为i + derta 的所有状态中取一个Max,所以可以开一个数组Max[i]代表高度为 i 时dp[i][j]的最大值,然后每一次求完dp[i][j]时动态更新Max[i]即可。所以转移方程就变成了
dp[i][j] = max(dp[i +1][j], Max[i +derta])
时间复杂度O(h * n)。
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<stack>
#include<queue>
#include<vector>
#include<cctype>
using namespace std;
#define space putchar(' ')
#define enter puts("")
#define Mem(a) memset(a, 0, sizeof(a))
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-;
const int max_hig = 2e3 + ;
const int maxn = 5e3 + ;
inline ll read()
{
ll ans = ;
char ch = getchar(), last = ' ';
while(!isdigit(ch)) {last = ch; ch = getchar();}
while(isdigit(ch)) {ans = (ans << ) + (ans << ) + ch - ''; ch = getchar();}
if(last == '-') ans = -ans;
return ans;
}
inline void write(ll x)
{
if(x < ) putchar('-'), x = -x;
if(x >= ) write(x / );
putchar(x % + '');
} int n, h, d;
int a[max_hig][maxn], dp[max_hig][maxn], Max[max_hig]; int main()
{
n = read(), h = read(), d = read();
for(int i = ; i <= n; ++i)
{
int x = read();
for(int j = ; j <= x; ++j) a[read()][i]++;
}
for(int i = h; i >= ; --i)
for(int j = ; j <= n; ++j)
{
dp[i][j] = dp[i + ][j];
if(i + d <= h) dp[i][j] = max(dp[i][j], Max[i + d]);
if(a[i][j]) dp[i][j] += a[i][j];
Max[i] = max(Max[i], dp[i][j]);
}
int ans = ;
for(int i = ; i <= n; ++i) ans = max(ans, dp[][i]);
write(ans); enter;
return ;
}
最新文章
- (转)浅谈Java中的equals和==
- CountDownLatch和CyclicBarrier 举例详解
- Linux 下三种方式设置环境变量
- 插件兼容CommonJS, AMD, CMD 和 原生 JS
- JSON数据行转列的应用
- Eclipse報錯:Could not find or load main class
- 【转】一篇很全面的freemarker教程---有空慢慢实践
- 将服务费用DIY到底----走出软件作坊:三五个人十来条枪 如何成为开发正规军(十)[转]
- [洛谷1580]yyy loves Easter_Egg I
- iOS开发-No matching provisioning profiles found解决方法
- sql优化(oracle)
- Java它配备了一个很好的工具2
- OpenStack及其构成简介
- 函数, lambda表达式
- Guava Cache源码解析
- 关于html+ashx开发中几个问题的解决方法
- HI258摄像头旋转配置问题
- python 类的属性__slots__ (了解一点点)
- [WeChall] Training: Encodings I (Training, Encoding)
- XamarinEssentials教程首选项Preferences判断项目是否存在