网站怎么做域名实名认证,龙华网站 建设信科网络,公众号官网登录,深圳最新出行政策[TOC](Potions (Hard Version) and (Easy Version))
一、Potions(Easy Version)
1、问题 2、分析#xff08;背包DP 贪心#xff09;
简而言之就是我们需要从左到右开始选数字#xff0c;选的过程中我们需要保证我们选的数字的和始终是大于等于0的#xff0c;在满足这个…[TOC](Potions (Hard Version) and (Easy Version))
一、Potions(Easy Version)
1、问题 2、分析背包DP 贪心
简而言之就是我们需要从左到右开始选数字选的过程中我们需要保证我们选的数字的和始终是大于等于0的在满足这个条件的情况下求出我们所选的数字的个数的最大值。
由于这个简单版本的数据范围是2000还是比较小的所以我们可以使用O(n2)O(n^2)O(n2)的DP来解决。
假设我们的DP数组是: f[i][j]f[i][j]f[i][j]
这里的一个难点就是这个数组的含义是什么
我们这里的定义是在前iii个数字里面选恰好选择jjj个数字时数字之和的最大值。
我们先来解释一下为什么我们要存储最大值。
假设我们在前iii个物品里选择了jjj个那么这jjj个数字的和越大我们后续的选择空间越大这是一种贪心的想法。
那么我们如何求出最后的结果呢
根据题目要求我们的f[i][j]≥0f[i][j]\geq 0f[i][j]≥0。
所以我们可以去遍历f[n][i]f[n][i]f[n][i]只要这个数大于等于0我们就可以让我们的ansians iansi。最后一个大于等于0的f[n][i]f[n][i]f[n][i]所对应的iii就是我们的答案。
转移方程 f[i][j]{f[i−1][j]max(f[i−1][j−1]a[i],f[i−1][j])f[i−1][j−1]≥0f[i][j] \begin{cases} f[i - 1][j]\\ max\bigg(f[i - 1][j - 1] a[i], f[i -1][j]\bigg)f[i- 1][j- 1]\geq 0 \end{cases} f[i][j]⎩⎨⎧f[i−1][j]max(f[i−1][j−1]a[i],f[i−1][j])f[i−1][j−1]≥0 因为只有在当前数字的和大于等于0的时候我们才能去选下一个。所以我们需要让f[i−1][j−1]f[i-1][j-1]f[i−1][j−1]大于0。
3、代码
#includebits/stdc.h
#define endl \n
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef pairint,int pii;
const int N 2010;
ll a[N], f[N][N];
void solve()
{int n;cin n;for(int i 1; i n; i )cin a[i];memset(f, 0xcf, sizeof f);f[0][0] 0;for(int i 1; i n; i ){for(int j 0; j i; j ){f[i][j] f[i - 1][j];if(j 1 f[i - 1][j - 1] 0)f[i][j] max(f[i - 1][j - 1] a[i], f[i][j]);}}int ans 0;for(int i 0; i n; i ){if(f[n][i] 0)ans i;}cout ans endl;
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);solve();
}二、Potions(Hard Version)
1、问题 2、分析反悔贪心
这道题和上一道题的唯一区别就是我们的数据范围变得很大所以二维DP数组是存储不下的即使我们逆序遍历从而优化掉一维的话我们的时间复杂度也是平方级别的依然过不了。
因此我们就只能想别的方法了。
这里采用的也是贪心策略。
我们从左到右开始枚举每一个数在枚举的过程中我们会发现正数一定是要选择的所以遇到正数我们就加上即可。
这里的重点是负数的选择。
从左到右枚举每一个数假设每一个数都选择当当前的总和小于0的时候我们就把从开始位置到当前位置之间的负数中最小的一个删掉。
为什么这样做呢
假设枚举到第iii个的时候总和sumsumsum从正数变成负数。再假设此时我们选择了kkk个数不算第iii个。
那么很明确的是sumsumsum是由于第iii个数的加入才变成了负数 说明第iii个数一定是负数。那么我们当然可以选择删除第iii个数这样的话我们就能保证sumsumsum依然是正数。
但不选第iii个数就是最优解吗其实不一定的。
如果在111到iii之间存在一个小于第iii个数的最小的负数。如果我们删除了这个最小的负数选择了第iii个数我们将这两个数字记作minminmin和ppp。那么此时的总和就是sum−minpsum-minpsum−minp由minminmin小于ppp所以p−minp-minp−min是大于0的。
而此时我们选了几个数呢选择第iii个数我们此时总共选了k1k1k1个数删除最小的负数即再减一所以总共还是选择了kkk个数。
其实很容易证明当我们经过上述操作后我们的sumsumsum是从111到iii中选择kkk个数时最大的数字和。式子sump−minvsump-minvsump−minv就可以证明因为minvminvminv是最小的所以这个式子是最大的。
也就是说通过上述的操作我们维护的都是选择kkk个数时的最优解sumsumsum最大。
通过刚才的easyeasyeasy版本的讲解我们也知道选择相同个数的数字时总和越大越好总和越大说明我们后续的选择越多。
不妨看出通过上面的操作我们的kkk是不受影响的 即这样调整不会使得我们的答案变小。
如果感性认知的话就是我们时刻保持最优解去看能不能喝下一瓶。
综上我们的做法可以描述为从左到右遍历利用总和sumsumsum记录只要sumsumsum小于0了我们就删除遍历过的数中的最小负数。
在一堆数字中选出一个最值我们可以使用优先队列。
我们的时间复杂度即O(nlogn)O(nlogn)O(nlogn)。
而我们发现这个贪心过程中我们出现了反悔的操作即我们一开始喝了一瓶但是后来发现喝的这一瓶不是最优解那么我们就反悔了这一瓶不喝了。这种贪心就被称为反悔贪心。
3、代码
#includebits/stdc.h
#define endl \n
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef pairint,int pii;
const int N 2e5 10;
ll a[N], f[N];
void solve()
{int n;cin n;for(int i 0; i n; i )cin a[i];priority_queueintq;ll ans 0, sum 0;for(int i 0; i n; i ){sum a[i];ans ;if(a[i] 0)q.push( - a[i]);if(sum 0){sum q.top();q.pop();ans --;}}cout ans endl;}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);solve();
}
